{"thread":{"id":"60826","subject":"[PATCH v6 00/16] bloom: changed-path Bloom filters v2 (& sundries)","startedAt":"2024-01-31T22:52:20Z","lastAt":"2024-06-25T17:40:18Z","messageCount":36,"participants":["Taylor Blau","SZEDER Gábor","Jiang Xin"],"isPatch":true,"patchVersion":6,"patchTotal":16},"messages":[{"id":"487669","messageId":"cover.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":null,"subject":"[PATCH v6 00/16] bloom: changed-path Bloom filters v2 (& sundries)","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:08Z","receivedAt":"2024-01-31T22:52:20Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"(Rebased onto the tip of 'master', which is now bc7ee2e5e1 (The twelfth\nbatch, 2024-01-30), at the time of writing).\n\nThis series is a minor reroll of the combined efforts of [1] and [2] to\nintroduce the v2 changed-path Bloom filters, which fixes a bug in our\nexisting implementation of murmur3 paths with non-ASCII characters (when\nthe \"char\" type is signed).\n\nThis version is nearly identical to the previous round, modulo some\npatch reorganization prompted by a test failure noticed by SZEDER [3].\nI'm still not sure how that failure got through, but this round fixes\nit, and I've double checked that 'git rebase -ix \"make test\"' passes on\nacross all revisions.\n\nThanks again to Jonathan, Peff, and SZEDER who have helped a great deal\nin assembling these patches. As usual, a range-diff is included below.\n\nThanks in advance for your review!\n\n[1]: https://lore.kernel.org/git/cover.1684790529.git.jonathantanmy@google.com/\n[2]: https://lore.kernel.org/git/cover.1691426160.git.me@ttaylorr.com/\n[3]: https://lore.kernel.org/git/20240129212614.GB9612@szeder.dev/\n\nJonathan Tan (1):\n gitformat-commit-graph: describe version 2 of BDAT\n\nTaylor Blau (15):\n t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`\n revision.c: consult Bloom filters for root commits\n commit-graph: ensure Bloom filters are read with consistent settings\n t/helper/test-read-graph.c: extract `dump_graph_info()`\n bloom.h: make `load_bloom_filter_from_graph()` public\n t/helper/test-read-graph: implement `bloom-filters` mode\n t4216: test changed path filters with high bit paths\n repo-settings: introduce commitgraph.changedPathsVersion\n bloom: annotate filters with hash version\n bloom: prepare to discard incompatible Bloom filters\n commit-graph: unconditionally load Bloom filters\n commit-graph: new Bloom filter version that fixes murmur3\n object.h: fix mis-aligned flag bits table\n commit-graph: reuse existing Bloom filters where possible\n bloom: introduce `deinit_bloom_filters()`\n\n Documentation/config/commitgraph.txt | 29 ++-\n Documentation/gitformat-commit-graph.txt | 9 +-\n bloom.c | 208 ++++++++++++++-\n bloom.h | 38 ++-\n commit-graph.c | 64 ++++-\n object.h | 3 +-\n oss-fuzz/fuzz-commit-graph.c | 2 +-\n repo-settings.c | 6 +-\n repository.h | 2 +-\n revision.c | 26 +-\n t/helper/test-bloom.c | 9 +-\n t/helper/test-read-graph.c | 67 ++++-\n t/t0095-bloom.sh | 8 +\n t/t4216-log-bloom.sh | 310 ++++++++++++++++++++++-\n 14 files changed, 723 insertions(+), 58 deletions(-)\n\nRange-diff against v5:\n 1: 6292e974c5 = 1: 9df34a2f4f t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`\n 2: 6437cf5888 = 2: a6dc377f1b revision.c: consult Bloom filters for root commits\n 3: d5a73b9fa6 ! 3: a77ab941bc commit-graph: ensure Bloom filters are read with consistent settings\n @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm\n +\tdone\n +'\n +\n -+test_expect_success 'ensure incompatible Bloom filters are ignored' '\n ++test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '\n +\t# Compute Bloom filters with \"unusual\" settings.\n +\tgit -C $repo rev-parse one >in &&\n +\tGIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \\\n 4: 85af5e80ef = 4: 56a9fdaff0 gitformat-commit-graph: describe version 2 of BDAT\n 5: b5ff3a9b34 = 5: 7484a82f7f t/helper/test-read-graph.c: extract `dump_graph_info()`\n 6: 1b45dc8d85 = 6: 48343f93a2 bloom.h: make `load_bloom_filter_from_graph()` public\n 7: 42b5126016 = 7: 286fd7dcdb t/helper/test-read-graph: implement `bloom-filters` mode\n 8: 2029a2e30c = 8: 7de7b89da0 t4216: test changed path filters with high bit paths\n 9: 79c6c3025a ! 9: b13c9b8ff9 repo-settings: introduce commitgraph.changedPathsVersion\n @@ repository.h: struct repo_settings {\n \tint gc_write_commit_graph;\n \tint fetch_write_commit_graph;\n \tint command_requires_full_index;\n -\n - ## t/t4216-log-bloom.sh ##\n -@@ t/t4216-log-bloom.sh: test_expect_success 'setup for mixed Bloom setting tests' '\n - \tdone\n - '\n - \n --test_expect_success 'ensure incompatible Bloom filters are ignored' '\n -+test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '\n - \t# Compute Bloom filters with \"unusual\" settings.\n - \tgit -C $repo rev-parse one >in &&\n - \tGIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \\\n -@@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible Bloom settings' '\n - \ttest_must_be_empty err\n - '\n - \n -+test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '\n -+\trm \"$repo/$graph\" &&\n -+\n -+\tgit -C $repo log --oneline --no-decorate -- $CENT >expect &&\n -+\n -+\t# Compute v1 Bloom filters for commits at the bottom.\n -+\tgit -C $repo rev-parse HEAD^ >in &&\n -+\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n -+\t\t--split in &&\n -+\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \\\n -+\t\t--stdin-commits --changed-paths --split=no-merge actual 2>err &&\n -+\ttest_cmp expect actual &&\n -+\n -+\tlayer=\"$(head -n 1 $repo/$chain)\" &&\n -+\tcat >expect.err <<-EOF &&\n -+\twarning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings\n -+\tEOF\n -+\ttest_cmp expect.err err\n -+'\n -+\n - get_first_changed_path_filter () {\n - \ttest-tool read-graph bloom-filters >filters.dat &&\n - \thead -n 1 filters.dat\n11: a73c77a5ba = 10: 09c44c51a5 bloom: annotate filters with hash version\n12: 0c62b36206 = 11: d4995ef600 bloom: prepare to discard incompatible Bloom filters\n13: ff348fc49d ! 12: c8e9bb7c88 commit-graph.c: unconditionally load Bloom filters\n @@ Metadata\n Author: Taylor Blau \n \n ## Commit message ##\n - commit-graph.c: unconditionally load Bloom filters\n + commit-graph: unconditionally load Bloom filters\n \n In an earlier commit, we began ignoring the Bloom data (\"BDAT\") chunk\n for commit-graphs whose Bloom filters were computed using a hash version\n - incompatible with the value of `commitGraph.changedPathVersion`.\n + incompatible with the value of `commitGraph.changedPathVersion`.\n \n Now that the Bloom API has been hardened to discard these incompatible\n filters (with the exception of low-level APIs), we can safely load these\n @@ Commit message\n \n ## commit-graph.c ##\n @@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,\n - \n + \tg->chunk_bloom_data_size = chunk_size;\n \thash_version = get_be32(chunk_start);\n \n --\tif (*c->commit_graph_changed_paths_version == -1)\n --\t\t*c->commit_graph_changed_paths_version = hash_version;\n --\telse if (hash_version != *c->commit_graph_changed_paths_version)\n +-\tif (hash_version != 1)\n -\t\treturn 0;\n -\n - \tg->chunk_bloom_data = chunk_start;\n - \tg->chunk_bloom_data_size = chunk_size;\n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n + \tg->bloom_filter_settings->hash_version = hash_version;\n + \tg->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);\n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n \tctx->write_generation_data = (get_configured_generation_version(r) == 2);\n \tctx->num_generation_data_overflows = 0;\n \n --\tbloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2\n --\t\t? 2 : 1;\n +\tbloom_settings.hash_version = r->settings.commit_graph_changed_paths_version;\n \tbloom_settings.bits_per_entry = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY\",\n \t\t\t\t\t\t bloom_settings.bits_per_entry);\n \tbloom_settings.num_hashes = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_NUM_HASHES\",\n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n \t\t/* We have changed-paths already. Keep them in the next graph */\n - \t\tif (g && g->bloom_filter_settings) {\n + \t\tif (g && g->chunk_bloom_data) {\n \t\t\tctx->changed_paths = 1;\n -\t\t\tctx->bloom_settings = g->bloom_filter_settings;\n +\n10: cfa5c358f8 ! 13: d2f11c082d commit-graph: new Bloom filter version that fixes murmur3\n @@ bloom.h: int load_bloom_filter_from_graph(struct commit_graph *g,\n \t\t size_t len,\n \n ## commit-graph.c ##\n -@@ commit-graph.c: static int graph_read_bloom_index(const unsigned char *chunk_start,\n - \treturn 0;\n - }\n - \n -+struct graph_read_bloom_data_context {\n -+\tstruct commit_graph *g;\n -+\tint *commit_graph_changed_paths_version;\n -+};\n -+\n - static int graph_read_bloom_data(const unsigned char *chunk_start,\n +@@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,\n \t\t\t\t size_t chunk_size, void *data)\n {\n --\tstruct commit_graph *g = data;\n -+\tstruct graph_read_bloom_data_context *c = data;\n -+\tstruct commit_graph *g = c->g;\n - \tuint32_t hash_version;\n + \tstruct commit_graph *g = data;\n +-\tuint32_t hash_version;\n \n \tif (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) {\n + \t\twarning(_(\"ignoring too-small changed-path chunk\"\n @@ commit-graph.c: static int graph_read_bloom_data(const unsigned char *chunk_start,\n - \t\treturn -1;\n - \t}\n \n -+\thash_version = get_be32(chunk_start);\n -+\n -+\tif (*c->commit_graph_changed_paths_version == -1)\n -+\t\t*c->commit_graph_changed_paths_version = hash_version;\n -+\telse if (hash_version != *c->commit_graph_changed_paths_version)\n -+\t\treturn 0;\n -+\n \tg->chunk_bloom_data = chunk_start;\n \tg->chunk_bloom_data_size = chunk_size;\n -\thash_version = get_be32(chunk_start);\n --\n --\tif (hash_version != 1)\n --\t\treturn 0;\n --\n + \n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n - \tg->bloom_filter_settings->hash_version = hash_version;\n +-\tg->bloom_filter_settings->hash_version = hash_version;\n ++\tg->bloom_filter_settings->hash_version = get_be32(chunk_start);\n \tg->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);\n -@@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repo_settings *s,\n - \t}\n - \n - \tif (s->commit_graph_changed_paths_version) {\n -+\t\tstruct graph_read_bloom_data_context context = {\n -+\t\t\t.g = graph,\n -+\t\t\t.commit_graph_changed_paths_version = &s->commit_graph_changed_paths_version\n -+\t\t};\n - \t\tread_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,\n - \t\t\t graph_read_bloom_index, graph);\n - \t\tread_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,\n --\t\t\t graph_read_bloom_data, graph);\n -+\t\t\t graph_read_bloom_data, &context);\n - \t}\n - \n - \tif (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {\n + \tg->bloom_filter_settings->bits_per_entry = get_be32(chunk_start + 8);\n + \tg->bloom_filter_settings->max_changed_paths = DEFAULT_BLOOM_MAX_CHANGES;\n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n \t}\n \tif (!commit_graph_compatible(r))\n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n \n \tCALLOC_ARRAY(ctx, 1);\n \tctx->r = r;\n -@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n - \tctx->write_generation_data = (get_configured_generation_version(r) == 2);\n - \tctx->num_generation_data_overflows = 0;\n - \n -+\tbloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2\n -+\t\t? 2 : 1;\n - \tbloom_settings.bits_per_entry = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY\",\n - \t\t\t\t\t\t bloom_settings.bits_per_entry);\n - \tbloom_settings.num_hashes = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_NUM_HASHES\",\n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n \t\tg = ctx->r->objects->commit_graph;\n \n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n -\t\tif (g && g->chunk_bloom_data) {\n +\t\tif (g && g->bloom_filter_settings) {\n \t\t\tctx->changed_paths = 1;\n - \t\t\tctx->bloom_settings = g->bloom_filter_settings;\n - \t\t}\n + \n + \t\t\t/* don't propagate the hash_version unless unspecified */\n \n ## t/helper/test-bloom.c ##\n @@ t/helper/test-bloom.c: static void get_bloom_filter_for_commit(const struct object_id *commit_oid)\n @@ t/t0095-bloom.sh: test_expect_success 'compute unseeded murmur3 hash for test st\n \tHashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|\n \n ## t/t4216-log-bloom.sh ##\n +@@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible Bloom settings' '\n + \ttest_must_be_empty err\n + '\n + \n ++test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '\n ++\trm \"$repo/$graph\" &&\n ++\n ++\tgit -C $repo log --oneline --no-decorate -- $CENT >expect &&\n ++\n ++\t# Compute v1 Bloom filters for commits at the bottom.\n ++\tgit -C $repo rev-parse HEAD^ >in &&\n ++\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n ++\t\t--split in &&\n ++\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \\\n ++\t\t--stdin-commits --changed-paths --split=no-merge actual 2>err &&\n ++\ttest_cmp expect actual &&\n ++\n ++\tlayer=\"$(head -n 1 $repo/$chain)\" &&\n ++\tcat >expect.err <<-EOF &&\n ++\twarning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings\n ++\tEOF\n ++\ttest_cmp expect.err err\n ++'\n ++\n + get_first_changed_path_filter () {\n + \ttest-tool read-graph bloom-filters >filters.dat &&\n + \thead -n 1 filters.dat\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when version 1 requested' '\n \t)\n '\n14: acc0a097b3 < -: ---------- commit-graph: drop unnecessary `graph_read_bloom_data_context`\n15: da401c8853 = 14: 9f54a376fb object.h: fix mis-aligned flag bits table\n16: 2674967309 = 15: 67991dea7c commit-graph: reuse existing Bloom filters where possible\n17: bea7ec7b3f ! 16: 12058a074d bloom: introduce `deinit_bloom_filters()`\n @@ bloom.h: void add_key_to_filter(const struct bloom_key *key,\n \tBLOOM_NOT_COMPUTED = (1 << 0),\n \n ## commit-graph.c ##\n -@@ commit-graph.c: struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)\n - void close_commit_graph(struct raw_object_store *o)\n - {\n +@@ commit-graph.c: void close_commit_graph(struct raw_object_store *o)\n + \t\treturn;\n + \n \tclear_commit_graph_data_slab(&commit_graph_data_slab);\n +\tdeinit_bloom_filters();\n \tfree_commit_graph(o->commit_graph);\n\nbase-commit: bc7ee2e5e16f0d1e710ef8fab3db59ab11f2bbe7\n-- \n2.43.0.509.g253f65a7fc\n"},{"id":"487670","messageId":"9df34a2f4f588c3ce998bbcd51fc83b93726787e.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 01/16] t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:20Z","receivedAt":"2024-01-31T22:52:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The existing implementation of test_bloom_filters_not_used() asserts\nthat the Bloom filter sub-system has not been initialized at all, by\nchecking for the absence of any data from it from trace2.\n\nIn the following commit, it will become possible to load Bloom filters\nwithout using them (e.g., because the `commitGraph.changedPathVersion`\nintroduced later in this series is incompatible with the hash version\nwith which the commit-graph's Bloom filters were written).\n\nWhen this is the case, it's possible to initialize the Bloom filter\nsub-system, while still not using any Bloom filters. When this is the\ncase, check that the data dump from the Bloom sub-system is all zeros,\nindicating that no filters were used.\n\nSigned-off-by: Taylor Blau \n---\n t/t4216-log-bloom.sh | 14 +++++++++++++-\n 1 file changed, 13 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 2ba0324a69..b7baf49d62 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -82,7 +82,19 @@ test_bloom_filters_used () {\n test_bloom_filters_not_used () {\n \tlog_args=$1\n \tsetup \"$log_args\" &&\n-\t! grep -q \"statistics:{\\\"filter_not_present\\\":\" \"$TRASH_DIRECTORY/trace.perf\" &&\n+\n+\tif grep -q \"statistics:{\\\"filter_not_present\\\":\" \"$TRASH_DIRECTORY/trace.perf\"\n+\tthen\n+\t\t# if the Bloom filter system is initialized, ensure that no\n+\t\t# filters were used\n+\t\tdata=\"statistics:{\"\n+\t\tdata=\"$data\\\"filter_not_present\\\":0,\"\n+\t\tdata=\"$data\\\"maybe\\\":0,\"\n+\t\tdata=\"$data\\\"definitely_not\\\":0,\"\n+\t\tdata=\"$data\\\"false_positive\\\":0}\"\n+\n+\t\tgrep -q \"$data\" \"$TRASH_DIRECTORY/trace.perf\"\n+\tfi &&\n \ttest_cmp log_wo_bloom log_w_bloom\n }\n \n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487671","messageId":"a6dc377f1b46d4afd442023426fc8dd5cd8ceb8e.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 02/16] revision.c: consult Bloom filters for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:23Z","receivedAt":"2024-01-31T22:52:25Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The commit-graph stores changed-path Bloom filters which represent the\nset of paths included in a tree-level diff between a commit's root tree\nand that of its parent.\n\nWhen a commit has no parents, the tree-diff is computed against that\ncommit's root tree and the empty tree. In other words, every path in\nthat commit's tree is stored in the Bloom filter (since they all appear\nin the diff).\n\nConsult these filters during pathspec-limited traversals in the function\n`rev_same_tree_as_empty()`. Doing so yields a performance improvement\nwhere we can avoid enumerating the full set of paths in a parentless\ncommit's root tree when we know that the path(s) of interest were not\nlisted in that commit's changed-path Bloom filter.\n\nSuggested-by: SZEDER Gábor \nOriginal-patch-by: Jonathan Tan \nSigned-off-by: Taylor Blau \n---\n revision.c | 26 ++++++++++++++++++++++----\n t/t4216-log-bloom.sh | 8 ++++++--\n 2 files changed, 28 insertions(+), 6 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 2424c9bd67..0e6f7d02b6 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -833,17 +833,28 @@ static int rev_compare_tree(struct rev_info *revs,\n \treturn tree_difference;\n }\n \n-static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n+static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,\n+\t\t\t\t int nth_parent)\n {\n \tstruct tree *t1 = repo_get_commit_tree(the_repository, commit);\n+\tint bloom_ret = -1;\n \n \tif (!t1)\n \t\treturn 0;\n \n+\tif (!nth_parent && revs->bloom_keys_nr) {\n+\t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n+\t\tif (!bloom_ret)\n+\t\t\treturn 1;\n+\t}\n+\n \ttree_difference = REV_TREE_SAME;\n \trevs->pruning.flags.has_changes = 0;\n \tdiff_tree_oid(NULL, &t1->object.oid, \"\", &revs->pruning);\n \n+\tif (bloom_ret == 1 && tree_difference == REV_TREE_SAME)\n+\t\tcount_bloom_filter_false_positive++;\n+\n \treturn tree_difference == REV_TREE_SAME;\n }\n \n@@ -881,7 +892,7 @@ static int compact_treesame(struct rev_info *revs, struct commit *commit, unsign\n \t\tif (nth_parent != 0)\n \t\t\tdie(\"compact_treesame %u\", nth_parent);\n \t\told_same = !!(commit->object.flags & TREESAME);\n-\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\tif (rev_same_tree_as_empty(revs, commit, nth_parent))\n \t\t\tcommit->object.flags |= TREESAME;\n \t\telse\n \t\t\tcommit->object.flags &= ~TREESAME;\n@@ -977,7 +988,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn;\n \n \tif (!commit->parents) {\n-\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\t/*\n+\t\t * Pretend as if we are comparing ourselves to the\n+\t\t * (non-existent) first parent of this commit object. Even\n+\t\t * though no such parent exists, its changed-path Bloom filter\n+\t\t * (if one exists) is relative to the empty tree, using Bloom\n+\t\t * filters is allowed here.\n+\t\t */\n+\t\tif (rev_same_tree_as_empty(revs, commit, 0))\n \t\t\tcommit->object.flags |= TREESAME;\n \t\treturn;\n \t}\n@@ -1058,7 +1076,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \n \t\tcase REV_TREE_NEW:\n \t\t\tif (revs->remove_empty_trees &&\n-\t\t\t rev_same_tree_as_empty(revs, p)) {\n+\t\t\t rev_same_tree_as_empty(revs, p, nth_parent)) {\n \t\t\t\t/* We are adding all the specified\n \t\t\t\t * paths from this parent, so the\n \t\t\t\t * history beyond this parent is not\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex b7baf49d62..cc6ebc8140 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -88,7 +88,11 @@ test_bloom_filters_not_used () {\n \t\t# if the Bloom filter system is initialized, ensure that no\n \t\t# filters were used\n \t\tdata=\"statistics:{\"\n-\t\tdata=\"$data\\\"filter_not_present\\\":0,\"\n+\t\t# unusable filters (e.g., those computed with a\n+\t\t# different value of commitGraph.changedPathsVersion)\n+\t\t# are counted in the filter_not_present bucket, so any\n+\t\t# value is OK there.\n+\t\tdata=\"$data\\\"filter_not_present\\\":[0-9][0-9]*,\"\n \t\tdata=\"$data\\\"maybe\\\":0,\"\n \t\tdata=\"$data\\\"definitely_not\\\":0,\"\n \t\tdata=\"$data\\\"false_positive\\\":0}\"\n@@ -175,7 +179,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '\n \n test_bloom_filters_used_when_some_filters_are_missing () {\n \tlog_args=$1\n-\tbloom_trace_prefix=\"statistics:{\\\"filter_not_present\\\":3,\\\"maybe\\\":6,\\\"definitely_not\\\":9\"\n+\tbloom_trace_prefix=\"statistics:{\\\"filter_not_present\\\":3,\\\"maybe\\\":6,\\\"definitely_not\\\":10\"\n \tsetup \"$log_args\" &&\n \tgrep -q \"$bloom_trace_prefix\" \"$TRASH_DIRECTORY/trace.perf\" &&\n \ttest_cmp log_wo_bloom log_w_bloom\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487672","messageId":"a77ab941bc8867a2a40e02a0f9be4194681aa6e1.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 03/16] commit-graph: ensure Bloom filters are read with consistent settings","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:26Z","receivedAt":"2024-01-31T22:52:28Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The changed-path Bloom filter mechanism is parameterized by a couple of\nvariables, notably the number of bits per hash (typically \"m\" in Bloom\nfilter literature) and the number of hashes themselves (typically \"k\").\n\nIt is critically important that filters are read with the Bloom filter\nsettings that they were written with. Failing to do so would mean that\neach query is liable to compute different fingerprints, meaning that the\nfilter itself could return a false negative. This goes against a basic\nassumption of using Bloom filters (that they may return false positives,\nbut never false negatives) and can lead to incorrect results.\n\nWe have some existing logic to carry forward existing Bloom filter\nsettings from one layer to the next. In `write_commit_graph()`, we have\nsomething like:\n\n if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {\n struct commit_graph *g = ctx->r->objects->commit_graph;\n\n /* We have changed-paths already. Keep them in the next graph */\n if (g && g->chunk_bloom_data) {\n ctx->changed_paths = 1;\n ctx->bloom_settings = g->bloom_filter_settings;\n }\n }\n\n, which drags forward Bloom filter settings across adjacent layers.\n\nThis doesn't quite address all cases, however, since it is possible for\nintermediate layers to contain no Bloom filters at all. For example,\nsuppose we have two layers in a commit-graph chain, say, {G1, G2}. If G1\ncontains Bloom filters, but G2 doesn't, a new G3 (whose base graph is\nG2) may be written with arbitrary Bloom filter settings, because we only\ncheck the immediately adjacent layer's settings for compatibility.\n\nThis behavior has existed since the introduction of changed-path Bloom\nfilters. But in practice, this is not such a big deal, since the only\nway up until this point to modify the Bloom filter settings at write\ntime is with the undocumented environment variables:\n\n - GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY\n - GIT_TEST_BLOOM_SETTINGS_NUM_HASHES\n - GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS\n\n(it is still possible to tweak MAX_CHANGED_PATHS between layers, but\nthis does not affect reads, so is allowed to differ across multiple\ngraph layers).\n\nBut in future commits, we will introduce another parameter to change the\nhash algorithm used to compute Bloom fingerprints itself. This will be\nexposed via a configuration setting, making this foot-gun easier to use.\n\nTo prevent this potential issue, validate that all layers of a split\ncommit-graph have compatible settings with the newest layer which\ncontains Bloom filters.\n\nReported-by: SZEDER Gábor \nOriginal-test-by: SZEDER Gábor \nSigned-off-by: Taylor Blau \n---\n commit-graph.c | 25 +++++++++++++++++\n t/t4216-log-bloom.sh | 65 +++++++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 89 insertions(+), 1 deletion(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 45417d7412..216cf03da1 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -543,6 +543,30 @@ static int validate_mixed_generation_chain(struct commit_graph *g)\n \treturn 0;\n }\n \n+static void validate_mixed_bloom_settings(struct commit_graph *g)\n+{\n+\tstruct bloom_filter_settings *settings = NULL;\n+\tfor (; g; g = g->base_graph) {\n+\t\tif (!g->bloom_filter_settings)\n+\t\t\tcontinue;\n+\t\tif (!settings) {\n+\t\t\tsettings = g->bloom_filter_settings;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry ||\n+\t\t g->bloom_filter_settings->num_hashes != settings->num_hashes) {\n+\t\t\tg->chunk_bloom_indexes = NULL;\n+\t\t\tg->chunk_bloom_data = NULL;\n+\t\t\tFREE_AND_NULL(g->bloom_filter_settings);\n+\n+\t\t\twarning(_(\"disabling Bloom filters for commit-graph \"\n+\t\t\t\t \"layer '%s' due to incompatible settings\"),\n+\t\t\t\toid_to_hex(&g->oid));\n+\t\t}\n+\t}\n+}\n+\n static int add_graph_to_chain(struct commit_graph *g,\n \t\t\t struct commit_graph *chain,\n \t\t\t struct object_id *oids,\n@@ -666,6 +690,7 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct repository *r,\n \t}\n \n \tvalidate_mixed_generation_chain(graph_chain);\n+\tvalidate_mixed_bloom_settings(graph_chain);\n \n \tfree(oids);\n \tfclose(fp);\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex cc6ebc8140..64737b6ee9 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -421,8 +421,71 @@ test_expect_success 'Bloom generation backfills empty commits' '\n \t)\n '\n \n+graph=.git/objects/info/commit-graph\n+graphdir=.git/objects/info/commit-graphs\n+chain=$graphdir/commit-graph-chain\n+\n+test_expect_success 'setup for mixed Bloom setting tests' '\n+\trepo=mixed-bloom-settings &&\n+\n+\tgit init $repo &&\n+\tfor i in one two three\n+\tdo\n+\t\ttest_commit -C $repo $i file || return 1\n+\tdone\n+'\n+\n+test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '\n+\t# Compute Bloom filters with \"unusual\" settings.\n+\tgit -C $repo rev-parse one >in &&\n+\tGIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \\\n+\t\t--stdin-commits --changed-paths --split in &&\n+\tgit -C $repo commit-graph write --stdin-commits --no-changed-paths \\\n+\t\t--split=no-merge in &&\n+\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n+\t\t--split=no-merge expect 2>err &&\n+\tgit -C $repo log --oneline --no-decorate -- file >actual 2>err &&\n+\ttest_cmp expect actual &&\n+\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err\n+'\n+\n+test_expect_success 'merge graph layers with incompatible Bloom settings' '\n+\t# Ensure that incompatible Bloom filters are ignored when\n+\t# merging existing layers.\n+\tgit -C $repo commit-graph write --reachable --changed-paths 2>err &&\n+\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err &&\n+\n+\ttest_path_is_file $repo/$graph &&\n+\ttest_dir_is_empty $repo/$graphdir &&\n+\n+\tgit -C $repo -c core.commitGraph=false log --oneline --no-decorate -- \\\n+\t\tfile >expect &&\n+\ttrace_out=\"$(pwd)/trace.perf\" &&\n+\tGIT_TRACE2_PERF=\"$trace_out\" \\\n+\t\tgit -C $repo log --oneline --no-decorate -- file >actual 2>err &&\n+\n+\ttest_cmp expect actual &&\n+\tgrep \"statistics:{\\\"filter_not_present\\\":0,\" trace.perf &&\n+\ttest_must_be_empty err\n+'\n+\n corrupt_graph () {\n-\tgraph=.git/objects/info/commit-graph &&\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n \tcorrupt_chunk_file $graph \"$@\"\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487673","messageId":"56a9fdaff02e8b4488a44d4995a25651f33ccc2c.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 04/16] gitformat-commit-graph: describe version 2 of BDAT","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:29Z","receivedAt":"2024-01-31T22:52:31Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"From: Jonathan Tan \n\nThe code change to Git to support version 2 will be done in subsequent\ncommits.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n Documentation/gitformat-commit-graph.txt | 9 ++++++---\n 1 file changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/gitformat-commit-graph.txt b/Documentation/gitformat-commit-graph.txt\nindex 31cad585e2..3e906e8030 100644\n--- a/Documentation/gitformat-commit-graph.txt\n+++ b/Documentation/gitformat-commit-graph.txt\n@@ -142,13 +142,16 @@ All multi-byte numbers are in network byte order.\n \n ==== Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]\n * It starts with header consisting of three unsigned 32-bit integers:\n- - Version of the hash algorithm being used. We currently only support\n-\tvalue 1 which corresponds to the 32-bit version of the murmur3 hash\n+ - Version of the hash algorithm being used. We currently support\n+\tvalue 2 which corresponds to the 32-bit version of the murmur3 hash\n \timplemented exactly as described in\n \thttps://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double\n \thashing technique using seed values 0x293ae76f and 0x7e646e2 as\n \tdescribed in https://doi.org/10.1007/978-3-540-30494-4_26 \"Bloom Filters\n-\tin Probabilistic Verification\"\n+\tin Probabilistic Verification\". Version 1 Bloom filters have a bug that appears\n+\twhen char is signed and the repository has path names that have characters >=\n+\t0x80; Git supports reading and writing them, but this ability will be removed\n+\tin a future version of Git.\n - The number of times a path is hashed and hence the number of bit positions\n \t that cumulatively determine whether a file is present in the commit.\n - The minimum number of bits 'b' per entry in the Bloom filter. If the filter\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487674","messageId":"7484a82f7f3dc2cae32fac90d6f8e94f3d46aa93.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 05/16] t/helper/test-read-graph.c: extract `dump_graph_info()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:31Z","receivedAt":"2024-01-31T22:52:34Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Prepare for the 'read-graph' test helper to perform other tasks besides\ndumping high-level information about the commit-graph by extracting its\nmain routine into a separate function.\n\nSigned-off-by: Taylor Blau \nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n t/helper/test-read-graph.c | 31 ++++++++++++++++++-------------\n 1 file changed, 18 insertions(+), 13 deletions(-)\n\ndiff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c\nindex 8c7a83f578..3375392f6c 100644\n--- a/t/helper/test-read-graph.c\n+++ b/t/helper/test-read-graph.c\n@@ -5,20 +5,8 @@\n #include \"bloom.h\"\n #include \"setup.h\"\n \n-int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n+static void dump_graph_info(struct commit_graph *graph)\n {\n-\tstruct commit_graph *graph = NULL;\n-\tstruct object_directory *odb;\n-\n-\tsetup_git_directory();\n-\todb = the_repository->objects->odb;\n-\n-\tprepare_repo_settings(the_repository);\n-\n-\tgraph = read_commit_graph_one(the_repository, odb);\n-\tif (!graph)\n-\t\treturn 1;\n-\n \tprintf(\"header: %08x %d %d %d %d\\n\",\n \t\tntohl(*(uint32_t*)graph->data),\n \t\t*(unsigned char*)(graph->data + 4),\n@@ -57,6 +45,23 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n \tif (graph->topo_levels)\n \t\tprintf(\" topo_levels\");\n \tprintf(\"\\n\");\n+}\n+\n+int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n+{\n+\tstruct commit_graph *graph = NULL;\n+\tstruct object_directory *odb;\n+\n+\tsetup_git_directory();\n+\todb = the_repository->objects->odb;\n+\n+\tprepare_repo_settings(the_repository);\n+\n+\tgraph = read_commit_graph_one(the_repository, odb);\n+\tif (!graph)\n+\t\treturn 1;\n+\n+\tdump_graph_info(graph);\n \n \tUNLEAK(graph);\n \n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487675","messageId":"48343f93a27eababbbf5ab1355906229d151a8b7.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 06/16] bloom.h: make `load_bloom_filter_from_graph()` public","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:34Z","receivedAt":"2024-01-31T22:52:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Prepare for a future commit to use the load_bloom_filter_from_graph()\nfunction directly to load specific Bloom filters out of the commit-graph\nfor manual inspection (to be used during tests).\n\nSigned-off-by: Taylor Blau \nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n bloom.c | 6 +++---\n bloom.h | 5 +++++\n 2 files changed, 8 insertions(+), 3 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex e529f7605c..401999ed3c 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -48,9 +48,9 @@ static int check_bloom_offset(struct commit_graph *g, uint32_t pos,\n \treturn -1;\n }\n \n-static int load_bloom_filter_from_graph(struct commit_graph *g,\n-\t\t\t\t\tstruct bloom_filter *filter,\n-\t\t\t\t\tuint32_t graph_pos)\n+int load_bloom_filter_from_graph(struct commit_graph *g,\n+\t\t\t\t struct bloom_filter *filter,\n+\t\t\t\t uint32_t graph_pos)\n {\n \tuint32_t lex_pos, start_index, end_index;\n \ndiff --git a/bloom.h b/bloom.h\nindex adde6dfe21..1e4f612d2c 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -3,6 +3,7 @@\n \n struct commit;\n struct repository;\n+struct commit_graph;\n \n struct bloom_filter_settings {\n \t/*\n@@ -68,6 +69,10 @@ struct bloom_key {\n \tuint32_t *hashes;\n };\n \n+int load_bloom_filter_from_graph(struct commit_graph *g,\n+\t\t\t\t struct bloom_filter *filter,\n+\t\t\t\t uint32_t graph_pos);\n+\n /*\n * Calculate the murmur3 32-bit hash value for the given data\n * using the given seed.\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487676","messageId":"286fd7dcdb99af9b06b2f8e9f9adfcdc6b7d70d8.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 07/16] t/helper/test-read-graph: implement `bloom-filters` mode","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:37Z","receivedAt":"2024-01-31T22:52:39Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Implement a mode of the \"read-graph\" test helper to dump out the\nhexadecimal contents of the Bloom filter(s) contained in a commit-graph.\n\nSigned-off-by: Taylor Blau \nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n t/helper/test-read-graph.c | 44 +++++++++++++++++++++++++++++++++-----\n 1 file changed, 39 insertions(+), 5 deletions(-)\n\ndiff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c\nindex 3375392f6c..da9ac8584d 100644\n--- a/t/helper/test-read-graph.c\n+++ b/t/helper/test-read-graph.c\n@@ -47,10 +47,32 @@ static void dump_graph_info(struct commit_graph *graph)\n \tprintf(\"\\n\");\n }\n \n-int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n+static void dump_graph_bloom_filters(struct commit_graph *graph)\n+{\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < graph->num_commits + graph->num_commits_in_base; i++) {\n+\t\tstruct bloom_filter filter = { 0 };\n+\t\tsize_t j;\n+\n+\t\tif (load_bloom_filter_from_graph(graph, &filter, i) < 0) {\n+\t\t\tfprintf(stderr, \"missing Bloom filter for graph \"\n+\t\t\t\t\"position %\"PRIu32\"\\n\", i);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tfor (j = 0; j < filter.len; j++)\n+\t\t\tprintf(\"%02x\", filter.data[j]);\n+\t\tif (filter.len)\n+\t\t\tprintf(\"\\n\");\n+\t}\n+}\n+\n+int cmd__read_graph(int argc, const char **argv)\n {\n \tstruct commit_graph *graph = NULL;\n \tstruct object_directory *odb;\n+\tint ret = 0;\n \n \tsetup_git_directory();\n \todb = the_repository->objects->odb;\n@@ -58,12 +80,24 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n \tprepare_repo_settings(the_repository);\n \n \tgraph = read_commit_graph_one(the_repository, odb);\n-\tif (!graph)\n-\t\treturn 1;\n+\tif (!graph) {\n+\t\tret = 1;\n+\t\tgoto done;\n+\t}\n \n-\tdump_graph_info(graph);\n+\tif (argc <= 1)\n+\t\tdump_graph_info(graph);\n+\telse if (!strcmp(argv[1], \"bloom-filters\"))\n+\t\tdump_graph_bloom_filters(graph);\n+\telse {\n+\t\tfprintf(stderr, \"unknown sub-command: '%s'\\n\", argv[1]);\n+\t\tret = 1;\n+\t}\n \n+done:\n \tUNLEAK(graph);\n \n-\treturn 0;\n+\treturn ret;\n }\n+\n+\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487677","messageId":"7de7b89da072513c6e095fccdcac92dae7cda14a.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 08/16] t4216: test changed path filters with high bit paths","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:40Z","receivedAt":"2024-01-31T22:52:42Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Subsequent commits will teach Git another version of changed path\nfilter that has different behavior with paths that contain at least\none character with its high bit set, so test the existing behavior as\na baseline.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n t/t4216-log-bloom.sh | 51 ++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 51 insertions(+)\n\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 64737b6ee9..93b8d096cf 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -485,6 +485,57 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '\n \ttest_must_be_empty err\n '\n \n+get_first_changed_path_filter () {\n+\ttest-tool read-graph bloom-filters >filters.dat &&\n+\thead -n 1 filters.dat\n+}\n+\n+# chosen to be the same under all Unicode normalization forms\n+CENT=$(printf \"\\302\\242\")\n+\n+test_expect_success 'set up repo with high bit path, version 1 changed-path' '\n+\tgit init highbit1 &&\n+\ttest_commit -C highbit1 c1 \"$CENT\" &&\n+\tgit -C highbit1 commit-graph write --reachable --changed-paths\n+'\n+\n+test_expect_success 'setup check value of version 1 changed-path' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\techo \"52a9\" >expect &&\n+\t\tget_first_changed_path_filter >actual\n+\t)\n+'\n+\n+# expect will not match actual if char is unsigned by default. Write the test\n+# in this way, so that a user running this test script can still see if the two\n+# files match. (It will appear as an ordinary success if they match, and a skip\n+# if not.)\n+if test_cmp highbit1/expect highbit1/actual\n+then\n+\ttest_set_prereq SIGNED_CHAR_BY_DEFAULT\n+fi\n+test_expect_success SIGNED_CHAR_BY_DEFAULT 'check value of version 1 changed-path' '\n+\t# Only the prereq matters for this test.\n+\ttrue\n+'\n+\n+test_expect_success 'setup make another commit' '\n+\t# \"git log\" does not use Bloom filters for root commits - see how, in\n+\t# revision.c, rev_compare_tree() (the only code path that eventually calls\n+\t# get_bloom_filter()) is only called by try_to_simplify_commit() when the commit\n+\t# has one parent. Therefore, make another commit so that we perform the tests on\n+\t# a non-root commit.\n+\ttest_commit -C highbit1 anotherc1 \"another$CENT\"\n+'\n+\n+test_expect_success 'version 1 changed-path used when version 1 requested' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n corrupt_graph () {\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487678","messageId":"b13c9b8ff95e5cb7c2b4bd48590762215f6c2fb4.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 09/16] repo-settings: introduce commitgraph.changedPathsVersion","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:43Z","receivedAt":"2024-01-31T22:52:45Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"A subsequent commit will introduce another version of the changed-path\nfilter in the commit graph file. In order to control which version to\nwrite (and read), a config variable is needed.\n\nTherefore, introduce this config variable. For forwards compatibility,\nteach Git to not read commit graphs when the config variable\nis set to an unsupported version. Because we teach Git this,\ncommitgraph.readChangedPaths is now redundant, so deprecate it and\ndefine its behavior in terms of the config variable we introduce.\n\nThis commit does not change the behavior of writing (Git writes changed\npath filters when explicitly instructed regardless of any config\nvariable), but a subsequent commit will restrict Git such that it will\nonly write when commitgraph.changedPathsVersion is a recognized value.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n Documentation/config/commitgraph.txt | 26 +++++++++++++++++++++++---\n commit-graph.c | 5 +++--\n oss-fuzz/fuzz-commit-graph.c | 2 +-\n repo-settings.c | 6 +++++-\n repository.h | 2 +-\n 5 files changed, 33 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt\nindex 30604e4a4c..e68cdededa 100644\n--- a/Documentation/config/commitgraph.txt\n+++ b/Documentation/config/commitgraph.txt\n@@ -9,6 +9,26 @@ commitGraph.maxNewFilters::\n \tcommit-graph write` (c.f., linkgit:git-commit-graph[1]).\n \n commitGraph.readChangedPaths::\n-\tIf true, then git will use the changed-path Bloom filters in the\n-\tcommit-graph file (if it exists, and they are present). Defaults to\n-\ttrue. See linkgit:git-commit-graph[1] for more information.\n+\tDeprecated. Equivalent to commitGraph.changedPathsVersion=-1 if true, and\n+\tcommitGraph.changedPathsVersion=0 if false. (If commitGraph.changedPathVersion\n+\tis also set, commitGraph.changedPathsVersion takes precedence.)\n+\n+commitGraph.changedPathsVersion::\n+\tSpecifies the version of the changed-path Bloom filters that Git will read and\n+\twrite. May be -1, 0 or 1. Note that values greater than 1 may be\n+\tincompatible with older versions of Git which do not yet understand\n+\tthose versions. Use caution when operating in a mixed-version\n+\tenvironment.\n++\n+Defaults to -1.\n++\n+If -1, Git will use the version of the changed-path Bloom filters in the\n+repository, defaulting to 1 if there are none.\n++\n+If 0, Git will not read any Bloom filters, and will write version 1 Bloom\n+filters when instructed to write.\n++\n+If 1, Git will only read version 1 Bloom filters, and will write version 1\n+Bloom filters.\n++\n+See linkgit:git-commit-graph[1] for more information.\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 216cf03da1..b80bf36720 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -459,7 +459,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,\n \t\t\tgraph->read_generation_data = 1;\n \t}\n \n-\tif (s->commit_graph_read_changed_paths) {\n+\tif (s->commit_graph_changed_paths_version) {\n \t\tread_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,\n \t\t\t graph_read_bloom_index, graph);\n \t\tread_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,\n@@ -555,7 +555,8 @@ static void validate_mixed_bloom_settings(struct commit_graph *g)\n \t\t}\n \n \t\tif (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry ||\n-\t\t g->bloom_filter_settings->num_hashes != settings->num_hashes) {\n+\t\t g->bloom_filter_settings->num_hashes != settings->num_hashes ||\n+\t\t g->bloom_filter_settings->hash_version != settings->hash_version) {\n \t\t\tg->chunk_bloom_indexes = NULL;\n \t\t\tg->chunk_bloom_data = NULL;\n \t\t\tFREE_AND_NULL(g->bloom_filter_settings);\ndiff --git a/oss-fuzz/fuzz-commit-graph.c b/oss-fuzz/fuzz-commit-graph.c\nindex 2992079dd9..325c0b991a 100644\n--- a/oss-fuzz/fuzz-commit-graph.c\n+++ b/oss-fuzz/fuzz-commit-graph.c\n@@ -19,7 +19,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)\n \t * possible.\n \t */\n \tthe_repository->settings.commit_graph_generation_version = 2;\n-\tthe_repository->settings.commit_graph_read_changed_paths = 1;\n+\tthe_repository->settings.commit_graph_changed_paths_version = 1;\n \tg = parse_commit_graph(&the_repository->settings, (void *)data, size);\n \trepo_clear(the_repository);\n \tfree_commit_graph(g);\ndiff --git a/repo-settings.c b/repo-settings.c\nindex 30cd478762..c821583fe5 100644\n--- a/repo-settings.c\n+++ b/repo-settings.c\n@@ -23,6 +23,7 @@ void prepare_repo_settings(struct repository *r)\n \tint value;\n \tconst char *strval;\n \tint manyfiles;\n+\tint read_changed_paths;\n \n \tif (!r->gitdir)\n \t\tBUG(\"Cannot add settings for uninitialized repository\");\n@@ -53,7 +54,10 @@ void prepare_repo_settings(struct repository *r)\n \t/* Commit graph config or default, does not cascade (simple) */\n \trepo_cfg_bool(r, \"core.commitgraph\", &r->settings.core_commit_graph, 1);\n \trepo_cfg_int(r, \"commitgraph.generationversion\", &r->settings.commit_graph_generation_version, 2);\n-\trepo_cfg_bool(r, \"commitgraph.readchangedpaths\", &r->settings.commit_graph_read_changed_paths, 1);\n+\trepo_cfg_bool(r, \"commitgraph.readchangedpaths\", &read_changed_paths, 1);\n+\trepo_cfg_int(r, \"commitgraph.changedpathsversion\",\n+\t\t &r->settings.commit_graph_changed_paths_version,\n+\t\t read_changed_paths ? -1 : 0);\n \trepo_cfg_bool(r, \"gc.writecommitgraph\", &r->settings.gc_write_commit_graph, 1);\n \trepo_cfg_bool(r, \"fetch.writecommitgraph\", &r->settings.fetch_write_commit_graph, 0);\n \ndiff --git a/repository.h b/repository.h\nindex 7a250a6605..1edc4d4a67 100644\n--- a/repository.h\n+++ b/repository.h\n@@ -32,7 +32,7 @@ struct repo_settings {\n \n \tint core_commit_graph;\n \tint commit_graph_generation_version;\n-\tint commit_graph_read_changed_paths;\n+\tint commit_graph_changed_paths_version;\n \tint gc_write_commit_graph;\n \tint fetch_write_commit_graph;\n \tint command_requires_full_index;\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487679","messageId":"09c44c51a53026d757a5d08acd9a7e0aa6288eb1.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 10/16] bloom: annotate filters with hash version","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:45Z","receivedAt":"2024-01-31T22:52:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In subsequent commits, we will want to load existing Bloom filters out\nof a commit-graph, even when the hash version they were computed with\ndoes not match the value of `commitGraph.changedPathVersion`.\n\nIn order to differentiate between the two, add a \"version\" field to each\nBloom filter.\n\nSigned-off-by: Taylor Blau \n---\n bloom.c | 11 ++++++++---\n bloom.h | 1 +\n 2 files changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 401999ed3c..e64e53bc4c 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -88,6 +88,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n \tfilter->data = (unsigned char *)(g->chunk_bloom_data +\n \t\t\t\t\tsizeof(unsigned char) * start_index +\n \t\t\t\t\tBLOOMDATA_CHUNK_HEADER_SIZE);\n+\tfilter->version = g->bloom_filter_settings->hash_version;\n \n \treturn 1;\n }\n@@ -210,11 +211,13 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,\n \treturn strcmp(e1->path, e2->path);\n }\n \n-static void init_truncated_large_filter(struct bloom_filter *filter)\n+static void init_truncated_large_filter(struct bloom_filter *filter,\n+\t\t\t\t\tint version)\n {\n \tfilter->data = xmalloc(1);\n \tfilter->data[0] = 0xFF;\n \tfilter->len = 1;\n+\tfilter->version = version;\n }\n \n struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n@@ -299,13 +302,15 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t}\n \n \t\tif (hashmap_get_size(&pathmap) > settings->max_changed_paths) {\n-\t\t\tinit_truncated_large_filter(filter);\n+\t\t\tinit_truncated_large_filter(filter,\n+\t\t\t\t\t\t settings->hash_version);\n \t\t\tif (computed)\n \t\t\t\t*computed |= BLOOM_TRUNC_LARGE;\n \t\t\tgoto cleanup;\n \t\t}\n \n \t\tfilter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;\n+\t\tfilter->version = settings->hash_version;\n \t\tif (!filter->len) {\n \t\t\tif (computed)\n \t\t\t\t*computed |= BLOOM_TRUNC_EMPTY;\n@@ -325,7 +330,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t} else {\n \t\tfor (i = 0; i < diff_queued_diff.nr; i++)\n \t\t\tdiff_free_filepair(diff_queued_diff.queue[i]);\n-\t\tinit_truncated_large_filter(filter);\n+\t\tinit_truncated_large_filter(filter, settings->hash_version);\n \n \t\tif (computed)\n \t\t\t*computed |= BLOOM_TRUNC_LARGE;\ndiff --git a/bloom.h b/bloom.h\nindex 1e4f612d2c..c9dd7d4022 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -53,6 +53,7 @@ struct bloom_filter_settings {\n struct bloom_filter {\n \tunsigned char *data;\n \tsize_t len;\n+\tint version;\n };\n \n /*\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487680","messageId":"d4995ef6005b2b00d4d42dc6bc1e65006ff6faba.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 11/16] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:48Z","receivedAt":"2024-01-31T22:52:50Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Callers use the inline `get_bloom_filter()` implementation as a thin\nwrapper around `get_or_compute_bloom_filter()`. The former calls the\nlatter with a value of \"0\" for `compute_if_not_present`, making\n`get_bloom_filter()` the default read-only path for fetching an existing\nBloom filter.\n\nCallers expect the value returned from `get_bloom_filter()` is usable,\nthat is that it's compatible with the configured value corresponding to\n`commitGraph.changedPathsVersion`.\n\nThis is OK, since the commit-graph machinery only initializes its BDAT\nchunk (thereby enabling it to service Bloom filter queries) when the\nBloom filter hash_version is compatible with our settings. So any value\nreturned by `get_bloom_filter()` is trivially useable.\n\nHowever, subsequent commits will load the BDAT chunk even when the Bloom\nfilters are built with incompatible hash versions. Prepare to handle\nthis by teaching `get_bloom_filter()` to discard filters that are\nincompatible with the configured hash version.\n\nCallers who wish to read incompatible filters (e.g., for upgrading\nfilters from v1 to v2) may use the lower level routine,\n`get_or_compute_bloom_filter()`.\n\nSigned-off-by: Taylor Blau \n---\n bloom.c | 20 +++++++++++++++++++-\n bloom.h | 20 ++++++++++++++++++--\n 2 files changed, 37 insertions(+), 3 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex e64e53bc4c..c24489dbcf 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -220,6 +220,23 @@ static void init_truncated_large_filter(struct bloom_filter *filter,\n \tfilter->version = version;\n }\n \n+struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n+{\n+\tstruct bloom_filter *filter;\n+\tint hash_version;\n+\n+\tfilter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL);\n+\tif (!filter)\n+\t\treturn NULL;\n+\n+\tprepare_repo_settings(r);\n+\thash_version = r->settings.commit_graph_changed_paths_version;\n+\n+\tif (!(hash_version == -1 || hash_version == filter->version))\n+\t\treturn NULL; /* unusable filter */\n+\treturn filter;\n+}\n+\n struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t struct commit *c,\n \t\t\t\t\t\t int compute_if_not_present,\n@@ -245,7 +262,8 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t filter, graph_pos);\n \t}\n \n-\tif (filter->data && filter->len)\n+\tif ((filter->data && filter->len) &&\n+\t (!settings || settings->hash_version == filter->version))\n \t\treturn filter;\n \tif (!compute_if_not_present)\n \t\treturn NULL;\ndiff --git a/bloom.h b/bloom.h\nindex c9dd7d4022..052a993aab 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -108,8 +108,24 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t const struct bloom_filter_settings *settings,\n \t\t\t\t\t\t enum bloom_filter_computed *computed);\n \n-#define get_bloom_filter(r, c) get_or_compute_bloom_filter( \\\n-\t(r), (c), 0, NULL, NULL)\n+/*\n+ * Find the Bloom filter associated with the given commit \"c\".\n+ *\n+ * If any of the following are true\n+ *\n+ * - the repository does not have a commit-graph, or\n+ * - the repository disables reading from the commit-graph, or\n+ * - the given commit does not have a Bloom filter computed, or\n+ * - there is a Bloom filter for commit \"c\", but it cannot be read\n+ * because the filter uses an incompatible version of murmur3\n+ *\n+ * , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding\n+ * Bloom filter will be returned.\n+ *\n+ * For callers who wish to inspect Bloom filters with incompatible hash\n+ * versions, use get_or_compute_bloom_filter().\n+ */\n+struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c);\n \n int bloom_filter_contains(const struct bloom_filter *filter,\n \t\t\t const struct bloom_key *key,\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487681","messageId":"c8e9bb7c88e6adb0dc28ea78db8065bd3cedb59c.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 12/16] commit-graph: unconditionally load Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:51Z","receivedAt":"2024-01-31T22:52:53Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In an earlier commit, we began ignoring the Bloom data (\"BDAT\") chunk\nfor commit-graphs whose Bloom filters were computed using a hash version\nincompatible with the value of `commitGraph.changedPathVersion`.\n\nNow that the Bloom API has been hardened to discard these incompatible\nfilters (with the exception of low-level APIs), we can safely load these\nBloom filters unconditionally.\n\nWe no longer want to return early from `graph_read_bloom_data()`, and\nsimilarly do not want to set the bloom_settings' `hash_version` field as\na side-effect. The latter is because we want to wait until we know which\nBloom settings we're using (either the defaults, from the GIT_TEST\nvariables, or from the previous commit-graph layer) before deciding what\nhash_version to use.\n\nIf we detect an existing BDAT chunk, we'll infer the rest of the\nsettings (e.g., number of hashes, bits per entry, and maximum number of\nchanged paths) from the earlier graph layer. The hash_version will be\ninferred from the previous layer as well, unless one has already been\nspecified via configuration.\n\nOnce all of that is done, we normalize the value of the hash_version to\neither \"1\" or \"2\".\n\nSigned-off-by: Taylor Blau \n---\n commit-graph.c | 14 ++++++++++----\n 1 file changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex b80bf36720..6c3fbae142 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -358,9 +358,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \tg->chunk_bloom_data_size = chunk_size;\n \thash_version = get_be32(chunk_start);\n \n-\tif (hash_version != 1)\n-\t\treturn 0;\n-\n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n \tg->bloom_filter_settings->hash_version = hash_version;\n \tg->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);\n@@ -2516,6 +2513,7 @@ int write_commit_graph(struct object_directory *odb,\n \tctx->write_generation_data = (get_configured_generation_version(r) == 2);\n \tctx->num_generation_data_overflows = 0;\n \n+\tbloom_settings.hash_version = r->settings.commit_graph_changed_paths_version;\n \tbloom_settings.bits_per_entry = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY\",\n \t\t\t\t\t\t bloom_settings.bits_per_entry);\n \tbloom_settings.num_hashes = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_NUM_HASHES\",\n@@ -2547,10 +2545,18 @@ int write_commit_graph(struct object_directory *odb,\n \t\t/* We have changed-paths already. Keep them in the next graph */\n \t\tif (g && g->chunk_bloom_data) {\n \t\t\tctx->changed_paths = 1;\n-\t\t\tctx->bloom_settings = g->bloom_filter_settings;\n+\n+\t\t\t/* don't propagate the hash_version unless unspecified */\n+\t\t\tif (bloom_settings.hash_version == -1)\n+\t\t\t\tbloom_settings.hash_version = g->bloom_filter_settings->hash_version;\n+\t\t\tbloom_settings.bits_per_entry = g->bloom_filter_settings->bits_per_entry;\n+\t\t\tbloom_settings.num_hashes = g->bloom_filter_settings->num_hashes;\n+\t\t\tbloom_settings.max_changed_paths = g->bloom_filter_settings->max_changed_paths;\n \t\t}\n \t}\n \n+\tbloom_settings.hash_version = bloom_settings.hash_version == 2 ? 2 : 1;\n+\n \tif (ctx->split) {\n \t\tstruct commit_graph *g = ctx->r->objects->commit_graph;\n \n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487682","messageId":"d2f11c082d3bf10d9127c330a7d59b7e47ac4f21.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 13/16] commit-graph: new Bloom filter version that fixes murmur3","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:54Z","receivedAt":"2024-01-31T22:52:56Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The murmur3 implementation in bloom.c has a bug when converting series\nof 4 bytes into network-order integers when char is signed (which is\ncontrollable by a compiler option, and the default signedness of char is\nplatform-specific). When a string contains characters with the high bit\nset, this bug causes results that, although internally consistent within\nGit, does not accord with other implementations of murmur3 (thus,\nthe changed path filters wouldn't be readable by other off-the-shelf\nimplementatios of murmur3) and even with Git binaries that were compiled\nwith different signedness of char. This bug affects both how Git writes\nchanged path filters to disk and how Git interprets changed path filters\non disk.\n\nTherefore, introduce a new version (2) of changed path filters that\ncorrects this problem. The existing version (1) is still supported and\nis still the default, but users should migrate away from it as soon\nas possible.\n\nBecause this bug only manifests with characters that have the high bit\nset, it may be possible that some (or all) commits in a given repo would\nhave the same changed path filter both before and after this fix is\napplied. However, in order to determine whether this is the case, the\nchanged paths would first have to be computed, at which point it is not\nmuch more expensive to just compute a new changed path filter.\n\nSo this patch does not include any mechanism to \"salvage\" changed path\nfilters from repositories. There is also no \"mixed\" mode - for each\ninvocation of Git, reading and writing changed path filters are done\nwith the same version number; this version number may be explicitly\nstated (typically if the user knows which version they need) or\nautomatically determined from the version of the existing changed path\nfilters in the repository.\n\nThere is a change in write_commit_graph(). graph_read_bloom_data()\nmakes it possible for chunk_bloom_data to be non-NULL but\nbloom_filter_settings to be NULL, which causes a segfault later on. I\nproduced such a segfault while developing this patch, but couldn't find\na way to reproduce it neither after this complete patch (or before),\nbut in any case it seemed like a good thing to include that might help\nfuture patch authors.\n\nThe value in t0095 was obtained from another murmur3 implementation\nusing the following Go source code:\n\n package main\n\n import \"fmt\"\n import \"github.com/spaolacci/murmur3\"\n\n func main() {\n fmt.Printf(\"%x\\n\", murmur3.Sum32([]byte(\"Hello world!\")))\n fmt.Printf(\"%x\\n\", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff}))\n }\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n Documentation/config/commitgraph.txt | 5 +-\n bloom.c | 69 ++++++++++++-\n bloom.h | 8 +-\n commit-graph.c | 13 ++-\n t/helper/test-bloom.c | 9 +-\n t/t0095-bloom.sh | 8 ++\n t/t4216-log-bloom.sh | 141 +++++++++++++++++++++++++++\n 7 files changed, 241 insertions(+), 12 deletions(-)\n\ndiff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt\nindex e68cdededa..7f8c9d6638 100644\n--- a/Documentation/config/commitgraph.txt\n+++ b/Documentation/config/commitgraph.txt\n@@ -15,7 +15,7 @@ commitGraph.readChangedPaths::\n \n commitGraph.changedPathsVersion::\n \tSpecifies the version of the changed-path Bloom filters that Git will read and\n-\twrite. May be -1, 0 or 1. Note that values greater than 1 may be\n+\twrite. May be -1, 0, 1, or 2. Note that values greater than 1 may be\n \tincompatible with older versions of Git which do not yet understand\n \tthose versions. Use caution when operating in a mixed-version\n \tenvironment.\n@@ -31,4 +31,7 @@ filters when instructed to write.\n If 1, Git will only read version 1 Bloom filters, and will write version 1\n Bloom filters.\n +\n+If 2, Git will only read version 2 Bloom filters, and will write version 2\n+Bloom filters.\n++\n See linkgit:git-commit-graph[1] for more information.\ndiff --git a/bloom.c b/bloom.c\nindex c24489dbcf..323d8012b8 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -100,7 +100,64 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n * Not considered to be cryptographically secure.\n * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm\n */\n-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)\n+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)\n+{\n+\tconst uint32_t c1 = 0xcc9e2d51;\n+\tconst uint32_t c2 = 0x1b873593;\n+\tconst uint32_t r1 = 15;\n+\tconst uint32_t r2 = 13;\n+\tconst uint32_t m = 5;\n+\tconst uint32_t n = 0xe6546b64;\n+\tint i;\n+\tuint32_t k1 = 0;\n+\tconst char *tail;\n+\n+\tint len4 = len / sizeof(uint32_t);\n+\n+\tuint32_t k;\n+\tfor (i = 0; i < len4; i++) {\n+\t\tuint32_t byte1 = (uint32_t)(unsigned char)data[4*i];\n+\t\tuint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8;\n+\t\tuint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16;\n+\t\tuint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24;\n+\t\tk = byte1 | byte2 | byte3 | byte4;\n+\t\tk *= c1;\n+\t\tk = rotate_left(k, r1);\n+\t\tk *= c2;\n+\n+\t\tseed ^= k;\n+\t\tseed = rotate_left(seed, r2) * m + n;\n+\t}\n+\n+\ttail = (data + len4 * sizeof(uint32_t));\n+\n+\tswitch (len & (sizeof(uint32_t) - 1)) {\n+\tcase 3:\n+\t\tk1 ^= ((uint32_t)(unsigned char)tail[2]) << 16;\n+\t\t/*-fallthrough*/\n+\tcase 2:\n+\t\tk1 ^= ((uint32_t)(unsigned char)tail[1]) << 8;\n+\t\t/*-fallthrough*/\n+\tcase 1:\n+\t\tk1 ^= ((uint32_t)(unsigned char)tail[0]) << 0;\n+\t\tk1 *= c1;\n+\t\tk1 = rotate_left(k1, r1);\n+\t\tk1 *= c2;\n+\t\tseed ^= k1;\n+\t\tbreak;\n+\t}\n+\n+\tseed ^= (uint32_t)len;\n+\tseed ^= (seed >> 16);\n+\tseed *= 0x85ebca6b;\n+\tseed ^= (seed >> 13);\n+\tseed *= 0xc2b2ae35;\n+\tseed ^= (seed >> 16);\n+\n+\treturn seed;\n+}\n+\n+static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)\n {\n \tconst uint32_t c1 = 0xcc9e2d51;\n \tconst uint32_t c2 = 0x1b873593;\n@@ -165,8 +222,14 @@ void fill_bloom_key(const char *data,\n \tint i;\n \tconst uint32_t seed0 = 0x293ae76f;\n \tconst uint32_t seed1 = 0x7e646e2c;\n-\tconst uint32_t hash0 = murmur3_seeded(seed0, data, len);\n-\tconst uint32_t hash1 = murmur3_seeded(seed1, data, len);\n+\tuint32_t hash0, hash1;\n+\tif (settings->hash_version == 2) {\n+\t\thash0 = murmur3_seeded_v2(seed0, data, len);\n+\t\thash1 = murmur3_seeded_v2(seed1, data, len);\n+\t} else {\n+\t\thash0 = murmur3_seeded_v1(seed0, data, len);\n+\t\thash1 = murmur3_seeded_v1(seed1, data, len);\n+\t}\n \n \tkey->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));\n \tfor (i = 0; i < settings->num_hashes; i++)\ndiff --git a/bloom.h b/bloom.h\nindex 052a993aab..bfe389e29c 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -8,9 +8,11 @@ struct commit_graph;\n struct bloom_filter_settings {\n \t/*\n \t * The version of the hashing technique being used.\n-\t * We currently only support version = 1 which is\n+\t * The newest version is 2, which is\n \t * the seeded murmur3 hashing technique implemented\n-\t * in bloom.c.\n+\t * in bloom.c. Bloom filters of version 1 were created\n+\t * with prior versions of Git, which had a bug in the\n+\t * implementation of the hash function.\n \t */\n \tuint32_t hash_version;\n \n@@ -81,7 +83,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n * Not considered to be cryptographically secure.\n * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm\n */\n-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);\n+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len);\n \n void fill_bloom_key(const char *data,\n \t\t size_t len,\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 6c3fbae142..6f9cab181e 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -344,7 +344,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \t\t\t\t size_t chunk_size, void *data)\n {\n \tstruct commit_graph *g = data;\n-\tuint32_t hash_version;\n \n \tif (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) {\n \t\twarning(_(\"ignoring too-small changed-path chunk\"\n@@ -356,10 +355,9 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \n \tg->chunk_bloom_data = chunk_start;\n \tg->chunk_bloom_data_size = chunk_size;\n-\thash_version = get_be32(chunk_start);\n \n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n-\tg->bloom_filter_settings->hash_version = hash_version;\n+\tg->bloom_filter_settings->hash_version = get_be32(chunk_start);\n \tg->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);\n \tg->bloom_filter_settings->bits_per_entry = get_be32(chunk_start + 8);\n \tg->bloom_filter_settings->max_changed_paths = DEFAULT_BLOOM_MAX_CHANGES;\n@@ -2501,6 +2499,13 @@ int write_commit_graph(struct object_directory *odb,\n \t}\n \tif (!commit_graph_compatible(r))\n \t\treturn 0;\n+\tif (r->settings.commit_graph_changed_paths_version < -1\n+\t || r->settings.commit_graph_changed_paths_version > 2) {\n+\t\twarning(_(\"attempting to write a commit-graph, but \"\n+\t\t\t \"'commitgraph.changedPathsVersion' (%d) is not supported\"),\n+\t\t\tr->settings.commit_graph_changed_paths_version);\n+\t\treturn 0;\n+\t}\n \n \tCALLOC_ARRAY(ctx, 1);\n \tctx->r = r;\n@@ -2543,7 +2548,7 @@ int write_commit_graph(struct object_directory *odb,\n \t\tg = ctx->r->objects->commit_graph;\n \n \t\t/* We have changed-paths already. Keep them in the next graph */\n-\t\tif (g && g->chunk_bloom_data) {\n+\t\tif (g && g->bloom_filter_settings) {\n \t\t\tctx->changed_paths = 1;\n \n \t\t\t/* don't propagate the hash_version unless unspecified */\ndiff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\nindex 1281e66876..eefc1668c7 100644\n--- a/t/helper/test-bloom.c\n+++ b/t/helper/test-bloom.c\n@@ -49,6 +49,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)\n \n static const char *bloom_usage = \"\\n\"\n \" test-tool bloom get_murmur3 \\n\"\n+\" test-tool bloom get_murmur3_seven_highbit\\n\"\n \" test-tool bloom generate_filter [...]\\n\"\n \" test-tool bloom get_filter_for_commit \\n\";\n \n@@ -63,7 +64,13 @@ int cmd__bloom(int argc, const char **argv)\n \t\tuint32_t hashed;\n \t\tif (argc < 3)\n \t\t\tusage(bloom_usage);\n-\t\thashed = murmur3_seeded(0, argv[2], strlen(argv[2]));\n+\t\thashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2]));\n+\t\tprintf(\"Murmur3 Hash with seed=0:0x%08x\\n\", hashed);\n+\t}\n+\n+\tif (!strcmp(argv[1], \"get_murmur3_seven_highbit\")) {\n+\t\tuint32_t hashed;\n+\t\thashed = murmur3_seeded_v2(0, \"\\x99\\xaa\\xbb\\xcc\\xdd\\xee\\xff\", 7);\n \t\tprintf(\"Murmur3 Hash with seed=0:0x%08x\\n\", hashed);\n \t}\n \ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex b567383eb8..c8d84ab606 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -29,6 +29,14 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'compute unseeded murmur3 hash for test string 3' '\n+\tcat >expect <<-\\EOF &&\n+\tMurmur3 Hash with seed=0:0xa183ccfd\n+\tEOF\n+\ttest-tool bloom get_murmur3_seven_highbit >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'compute bloom key for empty string' '\n \tcat >expect <<-\\EOF &&\n \tHashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 93b8d096cf..a7bf3a7dca 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -485,6 +485,33 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '\n \ttest_must_be_empty err\n '\n \n+test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '\n+\trm \"$repo/$graph\" &&\n+\n+\tgit -C $repo log --oneline --no-decorate -- $CENT >expect &&\n+\n+\t# Compute v1 Bloom filters for commits at the bottom.\n+\tgit -C $repo rev-parse HEAD^ >in &&\n+\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n+\t\t--split in &&\n+\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \\\n+\t\t--stdin-commits --changed-paths --split=no-merge actual 2>err &&\n+\ttest_cmp expect actual &&\n+\n+\tlayer=\"$(head -n 1 $repo/$chain)\" &&\n+\tcat >expect.err <<-EOF &&\n+\twarning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings\n+\tEOF\n+\ttest_cmp expect.err err\n+'\n+\n get_first_changed_path_filter () {\n \ttest-tool read-graph bloom-filters >filters.dat &&\n \thead -n 1 filters.dat\n@@ -536,6 +563,120 @@ test_expect_success 'version 1 changed-path used when version 1 requested' '\n \t)\n '\n \n+test_expect_success 'version 1 changed-path not used when version 2 requested' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\tgit config --add commitgraph.changedPathsVersion 2 &&\n+\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'version 1 changed-path used when autodetect requested' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '\n+\ttest_commit -C highbit1 c1double \"$CENT$CENT\" &&\n+\tgit -C highbit1 commit-graph write --reachable --changed-paths &&\n+\t(\n+\t\tcd highbit1 &&\n+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n+\t\techo \"options: bloom(1,10,7) read_generation_data\" >expect &&\n+\t\ttest-tool read-graph >full &&\n+\t\tgrep options full >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'set up repo with high bit path, version 2 changed-path' '\n+\tgit init highbit2 &&\n+\tgit -C highbit2 config --add commitgraph.changedPathsVersion 2 &&\n+\ttest_commit -C highbit2 c2 \"$CENT\" &&\n+\tgit -C highbit2 commit-graph write --reachable --changed-paths\n+'\n+\n+test_expect_success 'check value of version 2 changed-path' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\techo \"c01f\" >expect &&\n+\t\tget_first_changed_path_filter >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'setup make another commit' '\n+\t# \"git log\" does not use Bloom filters for root commits - see how, in\n+\t# revision.c, rev_compare_tree() (the only code path that eventually calls\n+\t# get_bloom_filter()) is only called by try_to_simplify_commit() when the commit\n+\t# has one parent. Therefore, make another commit so that we perform the tests on\n+\t# a non-root commit.\n+\ttest_commit -C highbit2 anotherc2 \"another$CENT\"\n+'\n+\n+test_expect_success 'version 2 changed-path used when version 2 requested' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'version 2 changed-path not used when version 1 requested' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\tgit config --add commitgraph.changedPathsVersion 1 &&\n+\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'version 2 changed-path used when autodetect requested' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' '\n+\ttest_commit -C highbit2 c2double \"$CENT$CENT\" &&\n+\tgit -C highbit2 commit-graph write --reachable --changed-paths &&\n+\t(\n+\t\tcd highbit2 &&\n+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n+\t\techo \"options: bloom(2,10,7) read_generation_data\" >expect &&\n+\t\ttest-tool read-graph >full &&\n+\t\tgrep options full >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '\n+\tgit init doublewrite &&\n+\ttest_commit -C doublewrite c \"$CENT\" &&\n+\tgit -C doublewrite config --add commitgraph.changedPathsVersion 1 &&\n+\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\tfor v in -2 3\n+\tdo\n+\t\tgit -C doublewrite config --add commitgraph.changedPathsVersion $v &&\n+\t\tgit -C doublewrite commit-graph write --reachable --changed-paths 2>err &&\n+\t\tcat >expect <<-EOF &&\n+\t\twarning: attempting to write a commit-graph, but ${SQ}commitgraph.changedPathsVersion${SQ} ($v) is not supported\n+\t\tEOF\n+\t\ttest_cmp expect err || return 1\n+\tdone &&\n+\tgit -C doublewrite config --add commitgraph.changedPathsVersion 2 &&\n+\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\t(\n+\t\tcd doublewrite &&\n+\t\techo \"c01f\" >expect &&\n+\t\tget_first_changed_path_filter >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n corrupt_graph () {\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487683","messageId":"9f54a376fb317e9df9a37c3de0c8f219d4768d0b.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 14/16] object.h: fix mis-aligned flag bits table","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:56Z","receivedAt":"2024-01-31T22:52:58Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Bit position 23 is one column too far to the left.\n\nSigned-off-by: Taylor Blau \n---\n object.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/object.h b/object.h\nindex 114d45954d..db25714b4e 100644\n--- a/object.h\n+++ b/object.h\n@@ -62,7 +62,7 @@ void object_array_init(struct object_array *array);\n \n /*\n * object flag allocation:\n- * revision.h: 0---------10 15 23------27\n+ * revision.h: 0---------10 15 23------27\n * fetch-pack.c: 01 67\n * negotiator/default.c: 2--5\n * walker.c: 0-2\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487684","messageId":"67991dea7cb54229da695e2b22aa2a24515d9eca.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 15/16] commit-graph: reuse existing Bloom filters where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:52:59Z","receivedAt":"2024-01-31T22:53:01Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In an earlier commit, a bug was described where it's possible for Git to\nproduce non-murmur3 hashes when the platform's \"char\" type is signed,\nand there are paths with characters whose highest bit is set (i.e. all\ncharacters >= 0x80).\n\nThat patch allows the caller to control which version of Bloom filters\nare read and written. However, even on platforms with a signed \"char\"\ntype, it is possible to reuse existing Bloom filters if and only if\nthere are no changed paths in any commit's first parent tree-diff whose\ncharacters have their highest bit set.\n\nWhen this is the case, we can reuse the existing filter without having\nto compute a new one. This is done by marking trees which are known to\nhave (or not have) any such paths. When a commit's root tree is verified\nto not have any such paths, we mark it as such and declare that the\ncommit's Bloom filter is reusable.\n\nNote that this heuristic only goes in one direction. If neither a commit\nnor its first parent have any paths in their trees with non-ASCII\ncharacters, then we know for certain that a path with non-ASCII\ncharacters will not appear in a tree-diff against that commit's first\nparent. The reverse isn't necessarily true: just because the tree-diff\ndoesn't contain any such paths does not imply that no such paths exist\nin either tree.\n\nSo we end up recomputing some Bloom filters that we don't strictly have\nto (i.e. their bits are the same no matter which version of murmur3 we\nuse). But culling these out is impossible, since we'd have to perform\nthe full tree-diff, which is the same effort as computing the Bloom\nfilter from scratch.\n\nBut because we can cache our results in each tree's flag bits, we can\noften avoid recomputing many filters, thereby reducing the time it takes\nto run\n\n $ git commit-graph write --changed-paths --reachable\n\nwhen upgrading from v1 to v2 Bloom filters.\n\nTo benchmark this, let's generate a commit-graph in linux.git with v1\nchanged-paths in generation order[^1]:\n\n $ git clone git@github.com:torvalds/linux.git\n $ cd linux\n $ git commit-graph write --reachable --changed-paths\n $ graph=\".git/objects/info/commit-graph\"\n $ mv $graph{,.bak}\n\nThen let's time how long it takes to go from v1 to v2 filters (with and\nwithout the upgrade path enabled), resetting the state of the\ncommit-graph each time:\n\n $ git config commitGraph.changedPathsVersion 2\n $ hyperfine -p 'cp -f $graph.bak $graph' -L v 0,1 \\\n 'GIT_TEST_UPGRADE_BLOOM_FILTERS={v} git.compile commit-graph write --reachable --changed-paths'\n\nOn linux.git (where there aren't any non-ASCII paths), the timings\nindicate that this patch represents a speed-up over recomputing all\nBloom filters from scratch:\n\n Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths\n Time (mean ± σ): 124.873 s ± 0.316 s [User: 124.081 s, System: 0.643 s]\n Range (min … max): 124.621 s … 125.227 s 3 runs\n\n Benchmark 2: GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths\n Time (mean ± σ): 79.271 s ± 0.163 s [User: 74.611 s, System: 4.521 s]\n Range (min … max): 79.112 s … 79.437 s 3 runs\n\n Summary\n 'GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths' ran\n 1.58 ± 0.01 times faster than 'GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths'\n\nOn git.git, we do have some non-ASCII paths, giving us a more modest\nimprovement from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up.\nOn my machine, the stats for git.git are:\n\n - 8,285 Bloom filters computed from scratch\n - 10 Bloom filters generated as empty\n - 4 Bloom filters generated as truncated due to too many changed paths\n - 65,114 Bloom filters were reused when transitioning from v1 to v2.\n\n[^1]: Note that this is is important, since `--stdin-packs` or\n `--stdin-commits` orders commits in the commit-graph by their pack\n position (with `--stdin-packs`) or in the raw input (with\n `--stdin-commits`).\n\n Since we compute Bloom filters in the same order that commits appear\n in the graph, we must see a commit's (first) parent before we process\n the commit itself. This is only guaranteed to happen when sorting\n commits by their generation number.\n\nSigned-off-by: Taylor Blau \n---\n bloom.c | 90 ++++++++++++++++++++++++++++++++++++++++++--\n bloom.h | 1 +\n commit-graph.c | 5 +++\n object.h | 1 +\n t/t4216-log-bloom.sh | 35 ++++++++++++++++-\n 5 files changed, 128 insertions(+), 4 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 323d8012b8..a1c616bc71 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -6,6 +6,9 @@\n #include \"commit-graph.h\"\n #include \"commit.h\"\n #include \"commit-slab.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+#include \"config.h\"\n \n define_commit_slab(bloom_filter_slab, struct bloom_filter);\n \n@@ -283,6 +286,73 @@ static void init_truncated_large_filter(struct bloom_filter *filter,\n \tfilter->version = version;\n }\n \n+#define VISITED (1u<<21)\n+#define HIGH_BITS (1u<<22)\n+\n+static int has_entries_with_high_bit(struct repository *r, struct tree *t)\n+{\n+\tif (parse_tree(t))\n+\t\treturn 1;\n+\n+\tif (!(t->object.flags & VISITED)) {\n+\t\tstruct tree_desc desc;\n+\t\tstruct name_entry entry;\n+\n+\t\tinit_tree_desc(&desc, t->buffer, t->size);\n+\t\twhile (tree_entry(&desc, &entry)) {\n+\t\t\tsize_t i;\n+\t\t\tfor (i = 0; i < entry.pathlen; i++) {\n+\t\t\t\tif (entry.path[i] & 0x80) {\n+\t\t\t\t\tt->object.flags |= HIGH_BITS;\n+\t\t\t\t\tgoto done;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\t\tstruct tree *sub = lookup_tree(r, &entry.oid);\n+\t\t\t\tif (sub && has_entries_with_high_bit(r, sub)) {\n+\t\t\t\t\tt->object.flags |= HIGH_BITS;\n+\t\t\t\t\tgoto done;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t}\n+\n+done:\n+\t\tt->object.flags |= VISITED;\n+\t}\n+\n+\treturn !!(t->object.flags & HIGH_BITS);\n+}\n+\n+static int commit_tree_has_high_bit_paths(struct repository *r,\n+\t\t\t\t\t struct commit *c)\n+{\n+\tstruct tree *t;\n+\tif (repo_parse_commit(r, c))\n+\t\treturn 1;\n+\tt = repo_get_commit_tree(r, c);\n+\tif (!t)\n+\t\treturn 1;\n+\treturn has_entries_with_high_bit(r, t);\n+}\n+\n+static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c,\n+\t\t\t\t\t struct bloom_filter *filter,\n+\t\t\t\t\t int hash_version)\n+{\n+\tstruct commit_list *p = c->parents;\n+\tif (commit_tree_has_high_bit_paths(r, c))\n+\t\treturn NULL;\n+\n+\tif (p && commit_tree_has_high_bit_paths(r, p->item))\n+\t\treturn NULL;\n+\n+\tfilter->version = hash_version;\n+\n+\treturn filter;\n+}\n+\n struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n {\n \tstruct bloom_filter *filter;\n@@ -325,9 +395,23 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t filter, graph_pos);\n \t}\n \n-\tif ((filter->data && filter->len) &&\n-\t (!settings || settings->hash_version == filter->version))\n-\t\treturn filter;\n+\tif (filter->data && filter->len) {\n+\t\tstruct bloom_filter *upgrade;\n+\t\tif (!settings || settings->hash_version == filter->version)\n+\t\t\treturn filter;\n+\n+\t\t/* version mismatch, see if we can upgrade */\n+\t\tif (compute_if_not_present &&\n+\t\t git_env_bool(\"GIT_TEST_UPGRADE_BLOOM_FILTERS\", 1)) {\n+\t\t\tupgrade = upgrade_filter(r, c, filter,\n+\t\t\t\t\t\t settings->hash_version);\n+\t\t\tif (upgrade) {\n+\t\t\t\tif (computed)\n+\t\t\t\t\t*computed |= BLOOM_UPGRADED;\n+\t\t\t\treturn upgrade;\n+\t\t\t}\n+\t\t}\n+\t}\n \tif (!compute_if_not_present)\n \t\treturn NULL;\n \ndiff --git a/bloom.h b/bloom.h\nindex bfe389e29c..e3a9b68905 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -102,6 +102,7 @@ enum bloom_filter_computed {\n \tBLOOM_COMPUTED = (1 << 1),\n \tBLOOM_TRUNC_LARGE = (1 << 2),\n \tBLOOM_TRUNC_EMPTY = (1 << 3),\n+\tBLOOM_UPGRADED = (1 << 4),\n };\n \n struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 6f9cab181e..320ac856ca 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1168,6 +1168,7 @@ struct write_commit_graph_context {\n \tint count_bloom_filter_not_computed;\n \tint count_bloom_filter_trunc_empty;\n \tint count_bloom_filter_trunc_large;\n+\tint count_bloom_filter_upgraded;\n };\n \n static int write_graph_chunk_fanout(struct hashfile *f,\n@@ -1775,6 +1776,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte\n \t\t\t ctx->count_bloom_filter_trunc_empty);\n \ttrace2_data_intmax(\"commit-graph\", ctx->r, \"filter-trunc-large\",\n \t\t\t ctx->count_bloom_filter_trunc_large);\n+\ttrace2_data_intmax(\"commit-graph\", ctx->r, \"filter-upgraded\",\n+\t\t\t ctx->count_bloom_filter_upgraded);\n }\n \n static void compute_bloom_filters(struct write_commit_graph_context *ctx)\n@@ -1816,6 +1819,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)\n \t\t\t\tctx->count_bloom_filter_trunc_empty++;\n \t\t\tif (computed & BLOOM_TRUNC_LARGE)\n \t\t\t\tctx->count_bloom_filter_trunc_large++;\n+\t\t} else if (computed & BLOOM_UPGRADED) {\n+\t\t\tctx->count_bloom_filter_upgraded++;\n \t\t} else if (computed & BLOOM_NOT_COMPUTED)\n \t\t\tctx->count_bloom_filter_not_computed++;\n \t\tctx->total_bloom_filter_data_size += filter\ndiff --git a/object.h b/object.h\nindex db25714b4e..2e5e08725f 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);\n * commit-reach.c: 16-----19\n * sha1-name.c: 20\n * list-objects-filter.c: 21\n+ * bloom.c: 2122\n * builtin/fsck.c: 0--3\n * builtin/gc.c: 0\n * builtin/index-pack.c: 2021\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex a7bf3a7dca..823d1cf773 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -222,6 +222,10 @@ test_filter_trunc_large () {\n \tgrep \"\\\"key\\\":\\\"filter-trunc-large\\\",\\\"value\\\":\\\"$1\\\"\" $2\n }\n \n+test_filter_upgraded () {\n+\tgrep \"\\\"key\\\":\\\"filter-upgraded\\\",\\\"value\\\":\\\"$1\\\"\" $2\n+}\n+\n test_expect_success 'correctly report changes over limit' '\n \tgit init limits &&\n \t(\n@@ -656,7 +660,13 @@ test_expect_success 'when writing another commit graph, preserve existing versio\n test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '\n \tgit init doublewrite &&\n \ttest_commit -C doublewrite c \"$CENT\" &&\n+\n \tgit -C doublewrite config --add commitgraph.changedPathsVersion 1 &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 1 trace2.txt &&\n+\ttest_filter_upgraded 0 trace2.txt &&\n+\n \tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n \tfor v in -2 3\n \tdo\n@@ -667,8 +677,13 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano\n \t\tEOF\n \t\ttest_cmp expect err || return 1\n \tdone &&\n+\n \tgit -C doublewrite config --add commitgraph.changedPathsVersion 2 &&\n-\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 1 trace2.txt &&\n+\ttest_filter_upgraded 0 trace2.txt &&\n+\n \t(\n \t\tcd doublewrite &&\n \t\techo \"c01f\" >expect &&\n@@ -677,6 +692,24 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano\n \t)\n '\n \n+test_expect_success 'when writing commit graph, reuse changed-path of another version where possible' '\n+\tgit init upgrade &&\n+\n+\ttest_commit -C upgrade base no-high-bits &&\n+\n+\tgit -C upgrade config --add commitgraph.changedPathsVersion 1 &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C upgrade commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 1 trace2.txt &&\n+\ttest_filter_upgraded 0 trace2.txt &&\n+\n+\tgit -C upgrade config --add commitgraph.changedPathsVersion 2 &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C upgrade commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 0 trace2.txt &&\n+\ttest_filter_upgraded 1 trace2.txt\n+'\n+\n corrupt_graph () {\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n-- \n2.43.0.509.g253f65a7fc\n\n"},{"id":"487685","messageId":"12058a074d8fa5a936f672c24943ebffc9c8ab0e.1706741516.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v6 16/16] bloom: introduce `deinit_bloom_filters()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-01-31T22:53:01Z","receivedAt":"2024-01-31T22:53:03Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"After we are done using Bloom filters, we do not currently clean up any\nmemory allocated by the commit slab used to store those filters in the\nfirst place.\n\nBesides the bloom_filter structures themselves, there is mostly nothing\nto free() in the first place, since in the read-only path all Bloom\nfilter's `data` members point to a memory mapped region in the\ncommit-graph file itself.\n\nBut when generating Bloom filters from scratch (or initializing\ntruncated filters) we allocate additional memory to store the filter's\ndata.\n\nKeep track of when we need to free() this additional chunk of memory by\nusing an extra pointer `to_free`. Most of the time this will be NULL\n(indicating that we are representing an existing Bloom filter stored in\na memory mapped region). When it is non-NULL, free it before discarding\nthe Bloom filters slab.\n\nSuggested-by: Jonathan Tan \nSigned-off-by: Taylor Blau \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n bloom.c | 16 +++++++++++++++-\n bloom.h | 3 +++\n commit-graph.c | 4 ++++\n 3 files changed, 22 insertions(+), 1 deletion(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex a1c616bc71..dbcc0f4f50 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -92,6 +92,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n \t\t\t\t\tsizeof(unsigned char) * start_index +\n \t\t\t\t\tBLOOMDATA_CHUNK_HEADER_SIZE);\n \tfilter->version = g->bloom_filter_settings->hash_version;\n+\tfilter->to_free = NULL;\n \n \treturn 1;\n }\n@@ -264,6 +265,18 @@ void init_bloom_filters(void)\n \tinit_bloom_filter_slab(&bloom_filters);\n }\n \n+static void free_one_bloom_filter(struct bloom_filter *filter)\n+{\n+\tif (!filter)\n+\t\treturn;\n+\tfree(filter->to_free);\n+}\n+\n+void deinit_bloom_filters(void)\n+{\n+\tdeep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter);\n+}\n+\n static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,\n \t\t const struct hashmap_entry *eptr,\n \t\t const struct hashmap_entry *entry_or_key,\n@@ -280,7 +293,7 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,\n static void init_truncated_large_filter(struct bloom_filter *filter,\n \t\t\t\t\tint version)\n {\n-\tfilter->data = xmalloc(1);\n+\tfilter->data = filter->to_free = xmalloc(1);\n \tfilter->data[0] = 0xFF;\n \tfilter->len = 1;\n \tfilter->version = version;\n@@ -482,6 +495,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\tfilter->len = 1;\n \t\t}\n \t\tCALLOC_ARRAY(filter->data, filter->len);\n+\t\tfilter->to_free = filter->data;\n \n \t\thashmap_for_each_entry(&pathmap, &iter, e, entry) {\n \t\t\tstruct bloom_key key;\ndiff --git a/bloom.h b/bloom.h\nindex e3a9b68905..d20e64bfbb 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -56,6 +56,8 @@ struct bloom_filter {\n \tunsigned char *data;\n \tsize_t len;\n \tint version;\n+\n+\tvoid *to_free;\n };\n \n /*\n@@ -96,6 +98,7 @@ void add_key_to_filter(const struct bloom_key *key,\n \t\t const struct bloom_filter_settings *settings);\n \n void init_bloom_filters(void);\n+void deinit_bloom_filters(void);\n \n enum bloom_filter_computed {\n \tBLOOM_NOT_COMPUTED = (1 << 0),\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 320ac856ca..6f5f8f158f 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -831,6 +831,7 @@ void close_commit_graph(struct raw_object_store *o)\n \t\treturn;\n \n \tclear_commit_graph_data_slab(&commit_graph_data_slab);\n+\tdeinit_bloom_filters();\n \tfree_commit_graph(o->commit_graph);\n \to->commit_graph = NULL;\n }\n@@ -2649,6 +2650,9 @@ int write_commit_graph(struct object_directory *odb,\n \n \tres = write_commit_graph_file(ctx);\n \n+\tif (ctx->changed_paths)\n+\t\tdeinit_bloom_filters();\n+\n \tif (ctx->split)\n \t\tmark_commit_graphs(ctx);\n \n-- \n2.43.0.509.g253f65a7fc\n"},{"id":"489335","messageId":"20240225221524.GA1940392@szeder.dev","threadId":"60826","inReplyTo":"d2f11c082d3bf10d9127c330a7d59b7e47ac4f21.1706741516.git.me@ttaylorr.com","subject":"Re: [PATCH v6 13/16] commit-graph: new Bloom filter version that fixes murmur3","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2024-02-25T22:15:24Z","receivedAt":"2024-02-25T22:15:27Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, Jan 31, 2024 at 05:52:54PM -0500, Taylor Blau wrote:\n> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\n> index 93b8d096cf..a7bf3a7dca 100755\n> --- a/t/t4216-log-bloom.sh\n> +++ b/t/t4216-log-bloom.sh\n> @@ -485,6 +485,33 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '\n> \ttest_must_be_empty err\n> '\n> \n> +test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '\n> +\trm \"$repo/$graph\" &&\n> +\n> +\tgit -C $repo log --oneline --no-decorate -- $CENT >expect &&\n\nThe $CENT variable is not set at this point in the test script.\nHowever, even if it were, the repository used in this test case\ndoesn't contain any file with that name.\n\n> +\n> +\t# Compute v1 Bloom filters for commits at the bottom.\n> +\tgit -C $repo rev-parse HEAD^ >in &&\n> +\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n> +\t\t--split +\n> +\t# Compute v2 Bloomfilters for the rest of the commits at the top.\n> +\tgit -C $repo rev-parse HEAD >in &&\n> +\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \\\n> +\t\t--stdin-commits --changed-paths --split=no-merge +\n> +\ttest_line_count = 2 $repo/$chain &&\n> +\n> +\tgit -C $repo log --oneline --no-decorate -- $CENT >actual 2>err &&\n> +\ttest_cmp expect actual &&\n> +\n> +\tlayer=\"$(head -n 1 $repo/$chain)\" &&\n> +\tcat >expect.err <<-EOF &&\n> +\twarning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings\n> +\tEOF\n> +\ttest_cmp expect.err err\n\nThe variable $repo is used 9 times in this test case. I think it\nwould be simpler and easier follow if it used a ( cd $repo && ... )\nsubshell, like many of the previous tests in this test script, \n\n> +'\n> +\n> get_first_changed_path_filter () {\n> \ttest-tool read-graph bloom-filters >filters.dat &&\n> \thead -n 1 filters.dat\n> @@ -536,6 +563,120 @@ test_expect_success 'version 1 changed-path used when version 1 requested' '\n> \t)\n> '\n> \n> +test_expect_success 'version 1 changed-path not used when version 2 requested' '\n> +\t(\n> +\t\tcd highbit1 &&\n> +\t\tgit config --add commitgraph.changedPathsVersion 2 &&\n> +\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n> +\t)\n> +'\n> +\n> +test_expect_success 'version 1 changed-path used when autodetect requested' '\n> +\t(\n> +\t\tcd highbit1 &&\n> +\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n> +\t\ttest_bloom_filters_used \"-- another$CENT\"\n> +\t)\n> +'\n> +\n> +test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '\n> +\ttest_commit -C highbit1 c1double \"$CENT$CENT\" &&\n> +\tgit -C highbit1 commit-graph write --reachable --changed-paths &&\n> +\t(\n> +\t\tcd highbit1 &&\n> +\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n> +\t\techo \"options: bloom(1,10,7) read_generation_data\" >expect &&\n> +\t\ttest-tool read-graph >full &&\n> +\t\tgrep options full >actual &&\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n> +\n> +test_expect_success 'set up repo with high bit path, version 2 changed-path' '\n> +\tgit init highbit2 &&\n> +\tgit -C highbit2 config --add commitgraph.changedPathsVersion 2 &&\n> +\ttest_commit -C highbit2 c2 \"$CENT\" &&\n> +\tgit -C highbit2 commit-graph write --reachable --changed-paths\n> +'\n> +\n> +test_expect_success 'check value of version 2 changed-path' '\n> +\t(\n> +\t\tcd highbit2 &&\n> +\t\techo \"c01f\" >expect &&\n> +\t\tget_first_changed_path_filter >actual &&\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n> +\n> +test_expect_success 'setup make another commit' '\n> +\t# \"git log\" does not use Bloom filters for root commits - see how, in\n> +\t# revision.c, rev_compare_tree() (the only code path that eventually calls\n> +\t# get_bloom_filter()) is only called by try_to_simplify_commit() when the commit\n> +\t# has one parent. Therefore, make another commit so that we perform the tests on\n> +\t# a non-root commit.\n> +\ttest_commit -C highbit2 anotherc2 \"another$CENT\"\n> +'\n> +\n> +test_expect_success 'version 2 changed-path used when version 2 requested' '\n> +\t(\n> +\t\tcd highbit2 &&\n> +\t\ttest_bloom_filters_used \"-- another$CENT\"\n> +\t)\n> +'\n> +\n> +test_expect_success 'version 2 changed-path not used when version 1 requested' '\n> +\t(\n> +\t\tcd highbit2 &&\n> +\t\tgit config --add commitgraph.changedPathsVersion 1 &&\n> +\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n> +\t)\n> +'\n> +\n> +test_expect_success 'version 2 changed-path used when autodetect requested' '\n> +\t(\n> +\t\tcd highbit2 &&\n> +\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n> +\t\ttest_bloom_filters_used \"-- another$CENT\"\n> +\t)\n> +'\n> +\n> +test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' '\n> +\ttest_commit -C highbit2 c2double \"$CENT$CENT\" &&\n> +\tgit -C highbit2 commit-graph write --reachable --changed-paths &&\n> +\t(\n> +\t\tcd highbit2 &&\n> +\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n> +\t\techo \"options: bloom(2,10,7) read_generation_data\" >expect &&\n> +\t\ttest-tool read-graph >full &&\n> +\t\tgrep options full >actual &&\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n> +\n> +test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '\n> +\tgit init doublewrite &&\n> +\ttest_commit -C doublewrite c \"$CENT\" &&\n> +\tgit -C doublewrite config --add commitgraph.changedPathsVersion 1 &&\n> +\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n> +\tfor v in -2 3\n> +\tdo\n> +\t\tgit -C doublewrite config --add commitgraph.changedPathsVersion $v &&\n> +\t\tgit -C doublewrite commit-graph write --reachable --changed-paths 2>err &&\n> +\t\tcat >expect <<-EOF &&\n> +\t\twarning: attempting to write a commit-graph, but ${SQ}commitgraph.changedPathsVersion${SQ} ($v) is not supported\n> +\t\tEOF\n> +\t\ttest_cmp expect err || return 1\n> +\tdone &&\n> +\tgit -C doublewrite config --add commitgraph.changedPathsVersion 2 &&\n> +\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n\nThe path 'doublewrite' is used 8 times in this test case before\nfinally cd-ing into that directory in a subshell...\n\n> +\t(\n> +\t\tcd doublewrite &&\n> +\t\techo \"c01f\" >expect &&\n> +\t\tget_first_changed_path_filter >actual &&\n> +\t\ttest_cmp expect actual\n> +\t)\n> +'\n> +\n> corrupt_graph () {\n> \ttest_when_finished \"rm -rf $graph\" &&\n> \tgit commit-graph write --reachable --changed-paths &&\n> -- \n> 2.43.0.509.g253f65a7fc\n> \n"},{"id":"489588","messageId":"CANYiYbGEbvJHyDG1cQ9gKuRxdcCfwED6N2Ddn-PtVGSsmwOs4Q@mail.gmail.com","threadId":"60826","inReplyTo":"d2f11c082d3bf10d9127c330a7d59b7e47ac4f21.1706741516.git.me@ttaylorr.com","subject":"Re: [PATCH v6 13/16] commit-graph: new Bloom filter version that fixes murmur3","fromName":"Jiang Xin","fromEmail":"worldhello.net@gmail.com","sentAt":"2024-02-28T00:11:25Z","receivedAt":"2024-02-28T00:11:38Z","isPatch":true,"sender":{"key":"worldhello.net@gmail.com","avatar":"https://avatars.githubusercontent.com/u/183860?v=4"},"body":"On Thu, Feb 1, 2024 at 9:50 AM Taylor Blau wrote:\n>\n> diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt\n> index e68cdededa..7f8c9d6638 100644\n> --- a/Documentation/config/commitgraph.txt\n> +++ b/Documentation/config/commitgraph.txt\n> @@ -15,7 +15,7 @@ commitGraph.readChangedPaths::\n>\n> commitGraph.changedPathsVersion::\n\nThe word commitGraph is in camelCase here.\n\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 6c3fbae142..6f9cab181e 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -2501,6 +2499,13 @@ int write_commit_graph(struct object_directory *odb,\n> }\n> if (!commit_graph_compatible(r))\n> return 0;\n> + if (r->settings.commit_graph_changed_paths_version < -1\n> + || r->settings.commit_graph_changed_paths_version > 2) {\n> + warning(_(\"attempting to write a commit-graph, but \"\n> + \"'commitgraph.changedPathsVersion' (%d) is not supported\"),\n\nTo fix mismatched config variable, s/commitgraph/commitGraph/\nSee: https://github.com/git-l10n/pot-changes/blob/pot/seen/2024-02-27.diff#L32\n\n--\nJiang Xin\n"},{"id":"497637","messageId":"cover.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1706741516.git.me@ttaylorr.com","subject":"[PATCH v7 00/16] bloom: changed-path Bloom filters v2 (& sundries)","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:01Z","receivedAt":"2024-06-25T17:39:08Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"(Rebased onto the tip of 'master', which is now 1e1586e4ed (The\nsixteenth batch, 2024-06-24) at the time of writing).\n\nThis series is another minor reroll of the combined efforts of [1] and\n[2] to introduce the v2 changed-path Bloom filters, which fixes a bug in\nour existing implementation of murmur3 paths with non-ASCII characters\n(when the \"char\" type is signed).\n\nThis version addresses the remaining comments from SZEDER around more\nthorough testing of merging commit-graph layers with incompatible Bloom\nfilters versions, and ensuring the result is as expected.\n\nThanks again to Jonathan, Peff, and SZEDER who have helped a great deal\nin assembling these patches. As usual, a range-diff is included below.\n\nThanks in advance for your review!\n\n[1]: https://lore.kernel.org/git/cover.1684790529.git.jonathantanmy@google.com/\n[2]: https://lore.kernel.org/git/cover.1691426160.git.me@ttaylorr.com/\n\nJonathan Tan (1):\n gitformat-commit-graph: describe version 2 of BDAT\n\nTaylor Blau (15):\n t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`\n revision.c: consult Bloom filters for root commits\n commit-graph: ensure Bloom filters are read with consistent settings\n t/helper/test-read-graph.c: extract `dump_graph_info()`\n bloom.h: make `load_bloom_filter_from_graph()` public\n t/helper/test-read-graph: implement `bloom-filters` mode\n t4216: test changed path filters with high bit paths\n repo-settings: introduce commitgraph.changedPathsVersion\n bloom: annotate filters with hash version\n bloom: prepare to discard incompatible Bloom filters\n commit-graph: unconditionally load Bloom filters\n commit-graph: new Bloom filter version that fixes murmur3\n object.h: fix mis-aligned flag bits table\n commit-graph: reuse existing Bloom filters where possible\n bloom: introduce `deinit_bloom_filters()`\n\n Documentation/config/commitgraph.txt | 29 +-\n Documentation/gitformat-commit-graph.txt | 9 +-\n bloom.c | 208 ++++++++++++++-\n bloom.h | 38 ++-\n commit-graph.c | 64 ++++-\n object.h | 3 +-\n oss-fuzz/fuzz-commit-graph.c | 2 +-\n repo-settings.c | 6 +-\n repository.h | 2 +-\n revision.c | 26 +-\n t/helper/test-bloom.c | 9 +-\n t/helper/test-read-graph.c | 67 ++++-\n t/t0095-bloom.sh | 8 +\n t/t4216-log-bloom.sh | 325 ++++++++++++++++++++++-\n 14 files changed, 738 insertions(+), 58 deletions(-)\n\nRange-diff against v6:\n 1: 9df34a2f4f = 1: ee651fee33 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`\n 2: a6dc377f1b = 2: 5d88ad6c90 revision.c: consult Bloom filters for root commits\n 3: a77ab941bc ! 3: f6cf5bfc4e commit-graph: ensure Bloom filters are read with consistent settings\n @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm\n +test_expect_success 'merge graph layers with incompatible Bloom settings' '\n +\t# Ensure that incompatible Bloom filters are ignored when\n +\t# merging existing layers.\n -+\tgit -C $repo commit-graph write --reachable --changed-paths 2>err &&\n ++\t>trace2.txt &&\n ++\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n ++\t\tgit -C $repo commit-graph write --reachable --changed-paths 2>err &&\n +\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err &&\n ++\tgrep \"{\\\"hash_version\\\":1,\\\"num_hashes\\\":7,\\\"bits_per_entry\\\":10,\\\"max_changed_paths\\\":512\" trace2.txt &&\n +\n +\ttest_path_is_file $repo/$graph &&\n +\ttest_dir_is_empty $repo/$graphdir &&\n 4: 56a9fdaff0 = 4: 0041600f31 gitformat-commit-graph: describe version 2 of BDAT\n 5: 7484a82f7f = 5: 6e7f317551 t/helper/test-read-graph.c: extract `dump_graph_info()`\n 6: 48343f93a2 = 6: ae74fbad3e bloom.h: make `load_bloom_filter_from_graph()` public\n 7: 286fd7dcdb = 7: 0dfd1a361e t/helper/test-read-graph: implement `bloom-filters` mode\n 8: 7de7b89da0 = 8: fbcaa686b1 t4216: test changed path filters with high bit paths\n 9: b13c9b8ff9 ! 9: 60c063ca4a repo-settings: introduce commitgraph.changedPathsVersion\n @@ commit-graph.c: static void validate_mixed_bloom_settings(struct commit_graph *g\n \n ## oss-fuzz/fuzz-commit-graph.c ##\n @@ oss-fuzz/fuzz-commit-graph.c: int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)\n - \t * possible.\n \t */\n + \trepo_set_hash_algo(the_repository, GIT_HASH_SHA1);\n \tthe_repository->settings.commit_graph_generation_version = 2;\n -\tthe_repository->settings.commit_graph_read_changed_paths = 1;\n +\tthe_repository->settings.commit_graph_changed_paths_version = 1;\n10: 09c44c51a5 = 10: ce3a15a517 bloom: annotate filters with hash version\n11: d4995ef600 = 11: 99ab9cf448 bloom: prepare to discard incompatible Bloom filters\n12: c8e9bb7c88 = 12: 99e66d1dba commit-graph: unconditionally load Bloom filters\n13: d2f11c082d ! 13: 2e945c3d2e commit-graph: new Bloom filter version that fixes murmur3\n @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,\n +\tif (r->settings.commit_graph_changed_paths_version < -1\n +\t || r->settings.commit_graph_changed_paths_version > 2) {\n +\t\twarning(_(\"attempting to write a commit-graph, but \"\n -+\t\t\t \"'commitgraph.changedPathsVersion' (%d) is not supported\"),\n ++\t\t\t \"'commitGraph.changedPathsVersion' (%d) is not supported\"),\n +\t\t\tr->settings.commit_graph_changed_paths_version);\n +\t\treturn 0;\n +\t}\n @@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible\n \ttest_must_be_empty err\n '\n \n ++# chosen to be the same under all Unicode normalization forms\n ++CENT=$(printf \"\\302\\242\")\n ++\n +test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '\n +\trm \"$repo/$graph\" &&\n +\n @@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible\n +\tcat >expect.err <<-EOF &&\n +\twarning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings\n +\tEOF\n -+\ttest_cmp expect.err err\n ++\ttest_cmp expect.err err &&\n ++\n ++\t# Merge the two layers with incompatible bloom filter versions,\n ++\t# ensuring that the v2 filters are used.\n ++\t>trace2.txt &&\n ++\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n ++\t\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write --reachable --changed-paths 2>err &&\n ++\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err &&\n ++\tgrep \"{\\\"hash_version\\\":2,\\\"num_hashes\\\":7,\\\"bits_per_entry\\\":10,\\\"max_changed_paths\\\":512\" trace2.txt\n +'\n +\n get_first_changed_path_filter () {\n \ttest-tool read-graph bloom-filters >filters.dat &&\n \thead -n 1 filters.dat\n + }\n + \n +-# chosen to be the same under all Unicode normalization forms\n +-CENT=$(printf \"\\302\\242\")\n +-\n + test_expect_success 'set up repo with high bit path, version 1 changed-path' '\n + \tgit init highbit1 &&\n + \ttest_commit -C highbit1 c1 \"$CENT\" &&\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when version 1 requested' '\n \t)\n '\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +test_expect_success 'version 1 changed-path not used when version 2 requested' '\n +\t(\n +\t\tcd highbit1 &&\n -+\t\tgit config --add commitgraph.changedPathsVersion 2 &&\n ++\t\tgit config --add commitGraph.changedPathsVersion 2 &&\n +\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n +\t)\n +'\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +test_expect_success 'version 1 changed-path used when autodetect requested' '\n +\t(\n +\t\tcd highbit1 &&\n -+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n ++\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n +\t\ttest_bloom_filters_used \"-- another$CENT\"\n +\t)\n +'\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +\tgit -C highbit1 commit-graph write --reachable --changed-paths &&\n +\t(\n +\t\tcd highbit1 &&\n -+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n ++\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n +\t\techo \"options: bloom(1,10,7) read_generation_data\" >expect &&\n +\t\ttest-tool read-graph >full &&\n +\t\tgrep options full >actual &&\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +\n +test_expect_success 'set up repo with high bit path, version 2 changed-path' '\n +\tgit init highbit2 &&\n -+\tgit -C highbit2 config --add commitgraph.changedPathsVersion 2 &&\n ++\tgit -C highbit2 config --add commitGraph.changedPathsVersion 2 &&\n +\ttest_commit -C highbit2 c2 \"$CENT\" &&\n +\tgit -C highbit2 commit-graph write --reachable --changed-paths\n +'\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +test_expect_success 'version 2 changed-path not used when version 1 requested' '\n +\t(\n +\t\tcd highbit2 &&\n -+\t\tgit config --add commitgraph.changedPathsVersion 1 &&\n ++\t\tgit config --add commitGraph.changedPathsVersion 1 &&\n +\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n +\t)\n +'\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +test_expect_success 'version 2 changed-path used when autodetect requested' '\n +\t(\n +\t\tcd highbit2 &&\n -+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n ++\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n +\t\ttest_bloom_filters_used \"-- another$CENT\"\n +\t)\n +'\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +\tgit -C highbit2 commit-graph write --reachable --changed-paths &&\n +\t(\n +\t\tcd highbit2 &&\n -+\t\tgit config --add commitgraph.changedPathsVersion -1 &&\n ++\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n +\t\techo \"options: bloom(2,10,7) read_generation_data\" >expect &&\n +\t\ttest-tool read-graph >full &&\n +\t\tgrep options full >actual &&\n @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers\n +test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '\n +\tgit init doublewrite &&\n +\ttest_commit -C doublewrite c \"$CENT\" &&\n -+\tgit -C doublewrite config --add commitgraph.changedPathsVersion 1 &&\n ++\tgit -C doublewrite config --add commitGraph.changedPathsVersion 1 &&\n +\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n +\tfor v in -2 3\n +\tdo\n -+\t\tgit -C doublewrite config --add commitgraph.changedPathsVersion $v &&\n ++\t\tgit -C doublewrite config --add commitGraph.changedPathsVersion $v &&\n +\t\tgit -C doublewrite commit-graph write --reachable --changed-paths 2>err &&\n +\t\tcat >expect <<-EOF &&\n -+\t\twarning: attempting to write a commit-graph, but ${SQ}commitgraph.changedPathsVersion${SQ} ($v) is not supported\n ++\t\twarning: attempting to write a commit-graph, but ${SQ}commitGraph.changedPathsVersion${SQ} ($v) is not supported\n +\t\tEOF\n +\t\ttest_cmp expect err || return 1\n +\tdone &&\n -+\tgit -C doublewrite config --add commitgraph.changedPathsVersion 2 &&\n ++\tgit -C doublewrite config --add commitGraph.changedPathsVersion 2 &&\n +\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n +\t(\n +\t\tcd doublewrite &&\n14: 9f54a376fb = 14: 242f023135 object.h: fix mis-aligned flag bits table\n15: 67991dea7c ! 15: 1b80023e57 commit-graph: reuse existing Bloom filters where possible\n @@ bloom.c: static void init_truncated_large_filter(struct bloom_filter *filter,\n +\t\tstruct tree_desc desc;\n +\t\tstruct name_entry entry;\n +\n -+\t\tinit_tree_desc(&desc, t->buffer, t->size);\n ++\t\tinit_tree_desc(&desc, &t->object.oid, t->buffer, t->size);\n +\t\twhile (tree_entry(&desc, &entry)) {\n +\t\t\tsize_t i;\n +\t\t\tfor (i = 0; i < entry.pathlen; i++) {\n @@ t/t4216-log-bloom.sh: test_expect_success 'when writing another commit graph, pr\n \tgit init doublewrite &&\n \ttest_commit -C doublewrite c \"$CENT\" &&\n +\n - \tgit -C doublewrite config --add commitgraph.changedPathsVersion 1 &&\n + \tgit -C doublewrite config --add commitGraph.changedPathsVersion 1 &&\n ++\t>trace2.txt &&\n +\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n +\t\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n +\ttest_filter_computed 1 trace2.txt &&\n @@ t/t4216-log-bloom.sh: test_expect_success 'when writing commit graph, do not reu\n \t\ttest_cmp expect err || return 1\n \tdone &&\n +\n - \tgit -C doublewrite config --add commitgraph.changedPathsVersion 2 &&\n + \tgit -C doublewrite config --add commitGraph.changedPathsVersion 2 &&\n -\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n ++\t>trace2.txt &&\n +\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n +\t\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n +\ttest_filter_computed 1 trace2.txt &&\n @@ t/t4216-log-bloom.sh: test_expect_success 'when writing commit graph, do not reu\n +\n +\ttest_commit -C upgrade base no-high-bits &&\n +\n -+\tgit -C upgrade config --add commitgraph.changedPathsVersion 1 &&\n ++\tgit -C upgrade config --add commitGraph.changedPathsVersion 1 &&\n ++\t>trace2.txt &&\n +\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n +\t\tgit -C upgrade commit-graph write --reachable --changed-paths &&\n +\ttest_filter_computed 1 trace2.txt &&\n +\ttest_filter_upgraded 0 trace2.txt &&\n +\n -+\tgit -C upgrade config --add commitgraph.changedPathsVersion 2 &&\n ++\tgit -C upgrade config --add commitGraph.changedPathsVersion 2 &&\n ++\t>trace2.txt &&\n +\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n +\t\tgit -C upgrade commit-graph write --reachable --changed-paths &&\n +\ttest_filter_computed 0 trace2.txt &&\n16: 12058a074d = 16: db9991f339 bloom: introduce `deinit_bloom_filters()`\n\nbase-commit: 1e1586e4ed626bde864339c10570bc0e73f0ab97\n-- \n2.45.2.664.g446e6a2b1f\n"},{"id":"497638","messageId":"ee651fee33d5788295ae8ca785d5a283c92481e7.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 01/16] t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:09Z","receivedAt":"2024-06-25T17:39:12Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The existing implementation of test_bloom_filters_not_used() asserts\nthat the Bloom filter sub-system has not been initialized at all, by\nchecking for the absence of any data from it from trace2.\n\nIn the following commit, it will become possible to load Bloom filters\nwithout using them (e.g., because the `commitGraph.changedPathVersion`\nintroduced later in this series is incompatible with the hash version\nwith which the commit-graph's Bloom filters were written).\n\nWhen this is the case, it's possible to initialize the Bloom filter\nsub-system, while still not using any Bloom filters. When this is the\ncase, check that the data dump from the Bloom sub-system is all zeros,\nindicating that no filters were used.\n\nSigned-off-by: Taylor Blau \n---\n t/t4216-log-bloom.sh | 14 +++++++++++++-\n 1 file changed, 13 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 2ba0324a69..b7baf49d62 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -82,7 +82,19 @@ test_bloom_filters_used () {\n test_bloom_filters_not_used () {\n \tlog_args=$1\n \tsetup \"$log_args\" &&\n-\t! grep -q \"statistics:{\\\"filter_not_present\\\":\" \"$TRASH_DIRECTORY/trace.perf\" &&\n+\n+\tif grep -q \"statistics:{\\\"filter_not_present\\\":\" \"$TRASH_DIRECTORY/trace.perf\"\n+\tthen\n+\t\t# if the Bloom filter system is initialized, ensure that no\n+\t\t# filters were used\n+\t\tdata=\"statistics:{\"\n+\t\tdata=\"$data\\\"filter_not_present\\\":0,\"\n+\t\tdata=\"$data\\\"maybe\\\":0,\"\n+\t\tdata=\"$data\\\"definitely_not\\\":0,\"\n+\t\tdata=\"$data\\\"false_positive\\\":0}\"\n+\n+\t\tgrep -q \"$data\" \"$TRASH_DIRECTORY/trace.perf\"\n+\tfi &&\n \ttest_cmp log_wo_bloom log_w_bloom\n }\n \n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497639","messageId":"5d88ad6c905c040322f360884b756ece83eefa66.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 02/16] revision.c: consult Bloom filters for root commits","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:13Z","receivedAt":"2024-06-25T17:39:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The commit-graph stores changed-path Bloom filters which represent the\nset of paths included in a tree-level diff between a commit's root tree\nand that of its parent.\n\nWhen a commit has no parents, the tree-diff is computed against that\ncommit's root tree and the empty tree. In other words, every path in\nthat commit's tree is stored in the Bloom filter (since they all appear\nin the diff).\n\nConsult these filters during pathspec-limited traversals in the function\n`rev_same_tree_as_empty()`. Doing so yields a performance improvement\nwhere we can avoid enumerating the full set of paths in a parentless\ncommit's root tree when we know that the path(s) of interest were not\nlisted in that commit's changed-path Bloom filter.\n\nSuggested-by: SZEDER Gábor \nOriginal-patch-by: Jonathan Tan \nSigned-off-by: Taylor Blau \n---\n revision.c | 26 ++++++++++++++++++++++----\n t/t4216-log-bloom.sh | 8 ++++++--\n 2 files changed, 28 insertions(+), 6 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex c68deb57ce..6931665b95 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -845,17 +845,28 @@ static int rev_compare_tree(struct rev_info *revs,\n \treturn tree_difference;\n }\n \n-static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit)\n+static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit,\n+\t\t\t\t int nth_parent)\n {\n \tstruct tree *t1 = repo_get_commit_tree(the_repository, commit);\n+\tint bloom_ret = -1;\n \n \tif (!t1)\n \t\treturn 0;\n \n+\tif (!nth_parent && revs->bloom_keys_nr) {\n+\t\tbloom_ret = check_maybe_different_in_bloom_filter(revs, commit);\n+\t\tif (!bloom_ret)\n+\t\t\treturn 1;\n+\t}\n+\n \ttree_difference = REV_TREE_SAME;\n \trevs->pruning.flags.has_changes = 0;\n \tdiff_tree_oid(NULL, &t1->object.oid, \"\", &revs->pruning);\n \n+\tif (bloom_ret == 1 && tree_difference == REV_TREE_SAME)\n+\t\tcount_bloom_filter_false_positive++;\n+\n \treturn tree_difference == REV_TREE_SAME;\n }\n \n@@ -893,7 +904,7 @@ static int compact_treesame(struct rev_info *revs, struct commit *commit, unsign\n \t\tif (nth_parent != 0)\n \t\t\tdie(\"compact_treesame %u\", nth_parent);\n \t\told_same = !!(commit->object.flags & TREESAME);\n-\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\tif (rev_same_tree_as_empty(revs, commit, nth_parent))\n \t\t\tcommit->object.flags |= TREESAME;\n \t\telse\n \t\t\tcommit->object.flags &= ~TREESAME;\n@@ -989,7 +1000,14 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \t\treturn;\n \n \tif (!commit->parents) {\n-\t\tif (rev_same_tree_as_empty(revs, commit))\n+\t\t/*\n+\t\t * Pretend as if we are comparing ourselves to the\n+\t\t * (non-existent) first parent of this commit object. Even\n+\t\t * though no such parent exists, its changed-path Bloom filter\n+\t\t * (if one exists) is relative to the empty tree, using Bloom\n+\t\t * filters is allowed here.\n+\t\t */\n+\t\tif (rev_same_tree_as_empty(revs, commit, 0))\n \t\t\tcommit->object.flags |= TREESAME;\n \t\treturn;\n \t}\n@@ -1070,7 +1088,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \n \t\tcase REV_TREE_NEW:\n \t\t\tif (revs->remove_empty_trees &&\n-\t\t\t rev_same_tree_as_empty(revs, p)) {\n+\t\t\t rev_same_tree_as_empty(revs, p, nth_parent)) {\n \t\t\t\t/* We are adding all the specified\n \t\t\t\t * paths from this parent, so the\n \t\t\t\t * history beyond this parent is not\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex b7baf49d62..cc6ebc8140 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -88,7 +88,11 @@ test_bloom_filters_not_used () {\n \t\t# if the Bloom filter system is initialized, ensure that no\n \t\t# filters were used\n \t\tdata=\"statistics:{\"\n-\t\tdata=\"$data\\\"filter_not_present\\\":0,\"\n+\t\t# unusable filters (e.g., those computed with a\n+\t\t# different value of commitGraph.changedPathsVersion)\n+\t\t# are counted in the filter_not_present bucket, so any\n+\t\t# value is OK there.\n+\t\tdata=\"$data\\\"filter_not_present\\\":[0-9][0-9]*,\"\n \t\tdata=\"$data\\\"maybe\\\":0,\"\n \t\tdata=\"$data\\\"definitely_not\\\":0,\"\n \t\tdata=\"$data\\\"false_positive\\\":0}\"\n@@ -175,7 +179,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '\n \n test_bloom_filters_used_when_some_filters_are_missing () {\n \tlog_args=$1\n-\tbloom_trace_prefix=\"statistics:{\\\"filter_not_present\\\":3,\\\"maybe\\\":6,\\\"definitely_not\\\":9\"\n+\tbloom_trace_prefix=\"statistics:{\\\"filter_not_present\\\":3,\\\"maybe\\\":6,\\\"definitely_not\\\":10\"\n \tsetup \"$log_args\" &&\n \tgrep -q \"$bloom_trace_prefix\" \"$TRASH_DIRECTORY/trace.perf\" &&\n \ttest_cmp log_wo_bloom log_w_bloom\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497640","messageId":"f6cf5bfc4eae2945cf2811172ccdb1293d4b0499.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 03/16] commit-graph: ensure Bloom filters are read with consistent settings","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:16Z","receivedAt":"2024-06-25T17:39:19Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The changed-path Bloom filter mechanism is parameterized by a couple of\nvariables, notably the number of bits per hash (typically \"m\" in Bloom\nfilter literature) and the number of hashes themselves (typically \"k\").\n\nIt is critically important that filters are read with the Bloom filter\nsettings that they were written with. Failing to do so would mean that\neach query is liable to compute different fingerprints, meaning that the\nfilter itself could return a false negative. This goes against a basic\nassumption of using Bloom filters (that they may return false positives,\nbut never false negatives) and can lead to incorrect results.\n\nWe have some existing logic to carry forward existing Bloom filter\nsettings from one layer to the next. In `write_commit_graph()`, we have\nsomething like:\n\n if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {\n struct commit_graph *g = ctx->r->objects->commit_graph;\n\n /* We have changed-paths already. Keep them in the next graph */\n if (g && g->chunk_bloom_data) {\n ctx->changed_paths = 1;\n ctx->bloom_settings = g->bloom_filter_settings;\n }\n }\n\n, which drags forward Bloom filter settings across adjacent layers.\n\nThis doesn't quite address all cases, however, since it is possible for\nintermediate layers to contain no Bloom filters at all. For example,\nsuppose we have two layers in a commit-graph chain, say, {G1, G2}. If G1\ncontains Bloom filters, but G2 doesn't, a new G3 (whose base graph is\nG2) may be written with arbitrary Bloom filter settings, because we only\ncheck the immediately adjacent layer's settings for compatibility.\n\nThis behavior has existed since the introduction of changed-path Bloom\nfilters. But in practice, this is not such a big deal, since the only\nway up until this point to modify the Bloom filter settings at write\ntime is with the undocumented environment variables:\n\n - GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY\n - GIT_TEST_BLOOM_SETTINGS_NUM_HASHES\n - GIT_TEST_BLOOM_SETTINGS_MAX_CHANGED_PATHS\n\n(it is still possible to tweak MAX_CHANGED_PATHS between layers, but\nthis does not affect reads, so is allowed to differ across multiple\ngraph layers).\n\nBut in future commits, we will introduce another parameter to change the\nhash algorithm used to compute Bloom fingerprints itself. This will be\nexposed via a configuration setting, making this foot-gun easier to use.\n\nTo prevent this potential issue, validate that all layers of a split\ncommit-graph have compatible settings with the newest layer which\ncontains Bloom filters.\n\nReported-by: SZEDER Gábor \nOriginal-test-by: SZEDER Gábor \nSigned-off-by: Taylor Blau \n---\n commit-graph.c | 25 ++++++++++++++++\n t/t4216-log-bloom.sh | 68 +++++++++++++++++++++++++++++++++++++++++++-\n 2 files changed, 92 insertions(+), 1 deletion(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 595a349c56..3d89febae4 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -543,6 +543,30 @@ static int validate_mixed_generation_chain(struct commit_graph *g)\n \treturn 0;\n }\n \n+static void validate_mixed_bloom_settings(struct commit_graph *g)\n+{\n+\tstruct bloom_filter_settings *settings = NULL;\n+\tfor (; g; g = g->base_graph) {\n+\t\tif (!g->bloom_filter_settings)\n+\t\t\tcontinue;\n+\t\tif (!settings) {\n+\t\t\tsettings = g->bloom_filter_settings;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry ||\n+\t\t g->bloom_filter_settings->num_hashes != settings->num_hashes) {\n+\t\t\tg->chunk_bloom_indexes = NULL;\n+\t\t\tg->chunk_bloom_data = NULL;\n+\t\t\tFREE_AND_NULL(g->bloom_filter_settings);\n+\n+\t\t\twarning(_(\"disabling Bloom filters for commit-graph \"\n+\t\t\t\t \"layer '%s' due to incompatible settings\"),\n+\t\t\t\toid_to_hex(&g->oid));\n+\t\t}\n+\t}\n+}\n+\n static int add_graph_to_chain(struct commit_graph *g,\n \t\t\t struct commit_graph *chain,\n \t\t\t struct object_id *oids,\n@@ -666,6 +690,7 @@ struct commit_graph *load_commit_graph_chain_fd_st(struct repository *r,\n \t}\n \n \tvalidate_mixed_generation_chain(graph_chain);\n+\tvalidate_mixed_bloom_settings(graph_chain);\n \n \tfree(oids);\n \tfclose(fp);\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex cc6ebc8140..c1977961d0 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -421,8 +421,74 @@ test_expect_success 'Bloom generation backfills empty commits' '\n \t)\n '\n \n+graph=.git/objects/info/commit-graph\n+graphdir=.git/objects/info/commit-graphs\n+chain=$graphdir/commit-graph-chain\n+\n+test_expect_success 'setup for mixed Bloom setting tests' '\n+\trepo=mixed-bloom-settings &&\n+\n+\tgit init $repo &&\n+\tfor i in one two three\n+\tdo\n+\t\ttest_commit -C $repo $i file || return 1\n+\tdone\n+'\n+\n+test_expect_success 'ensure Bloom filters with incompatible settings are ignored' '\n+\t# Compute Bloom filters with \"unusual\" settings.\n+\tgit -C $repo rev-parse one >in &&\n+\tGIT_TEST_BLOOM_SETTINGS_NUM_HASHES=3 git -C $repo commit-graph write \\\n+\t\t--stdin-commits --changed-paths --split in &&\n+\tgit -C $repo commit-graph write --stdin-commits --no-changed-paths \\\n+\t\t--split=no-merge in &&\n+\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n+\t\t--split=no-merge expect 2>err &&\n+\tgit -C $repo log --oneline --no-decorate -- file >actual 2>err &&\n+\ttest_cmp expect actual &&\n+\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err\n+'\n+\n+test_expect_success 'merge graph layers with incompatible Bloom settings' '\n+\t# Ensure that incompatible Bloom filters are ignored when\n+\t# merging existing layers.\n+\t>trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C $repo commit-graph write --reachable --changed-paths 2>err &&\n+\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err &&\n+\tgrep \"{\\\"hash_version\\\":1,\\\"num_hashes\\\":7,\\\"bits_per_entry\\\":10,\\\"max_changed_paths\\\":512\" trace2.txt &&\n+\n+\ttest_path_is_file $repo/$graph &&\n+\ttest_dir_is_empty $repo/$graphdir &&\n+\n+\tgit -C $repo -c core.commitGraph=false log --oneline --no-decorate -- \\\n+\t\tfile >expect &&\n+\ttrace_out=\"$(pwd)/trace.perf\" &&\n+\tGIT_TRACE2_PERF=\"$trace_out\" \\\n+\t\tgit -C $repo log --oneline --no-decorate -- file >actual 2>err &&\n+\n+\ttest_cmp expect actual &&\n+\tgrep \"statistics:{\\\"filter_not_present\\\":0,\" trace.perf &&\n+\ttest_must_be_empty err\n+'\n+\n corrupt_graph () {\n-\tgraph=.git/objects/info/commit-graph &&\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n \tcorrupt_chunk_file $graph \"$@\"\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497641","messageId":"0041600f31d23f149c20a648bbb5cd61561d9488.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 04/16] gitformat-commit-graph: describe version 2 of BDAT","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:34Z","receivedAt":"2024-06-25T17:39:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"From: Jonathan Tan \n\nThe code change to Git to support version 2 will be done in subsequent\ncommits.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n Documentation/gitformat-commit-graph.txt | 9 ++++++---\n 1 file changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/Documentation/gitformat-commit-graph.txt b/Documentation/gitformat-commit-graph.txt\nindex 31cad585e2..3e906e8030 100644\n--- a/Documentation/gitformat-commit-graph.txt\n+++ b/Documentation/gitformat-commit-graph.txt\n@@ -142,13 +142,16 @@ All multi-byte numbers are in network byte order.\n \n ==== Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]\n * It starts with header consisting of three unsigned 32-bit integers:\n- - Version of the hash algorithm being used. We currently only support\n-\tvalue 1 which corresponds to the 32-bit version of the murmur3 hash\n+ - Version of the hash algorithm being used. We currently support\n+\tvalue 2 which corresponds to the 32-bit version of the murmur3 hash\n \timplemented exactly as described in\n \thttps://en.wikipedia.org/wiki/MurmurHash#Algorithm and the double\n \thashing technique using seed values 0x293ae76f and 0x7e646e2 as\n \tdescribed in https://doi.org/10.1007/978-3-540-30494-4_26 \"Bloom Filters\n-\tin Probabilistic Verification\"\n+\tin Probabilistic Verification\". Version 1 Bloom filters have a bug that appears\n+\twhen char is signed and the repository has path names that have characters >=\n+\t0x80; Git supports reading and writing them, but this ability will be removed\n+\tin a future version of Git.\n - The number of times a path is hashed and hence the number of bit positions\n \t that cumulatively determine whether a file is present in the commit.\n - The minimum number of bits 'b' per entry in the Bloom filter. If the filter\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497642","messageId":"6e7f317551d31ee38bfb2b8abe8268898158b161.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 05/16] t/helper/test-read-graph.c: extract `dump_graph_info()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:37Z","receivedAt":"2024-06-25T17:39:40Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Prepare for the 'read-graph' test helper to perform other tasks besides\ndumping high-level information about the commit-graph by extracting its\nmain routine into a separate function.\n\nSigned-off-by: Taylor Blau \nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n t/helper/test-read-graph.c | 31 ++++++++++++++++++-------------\n 1 file changed, 18 insertions(+), 13 deletions(-)\n\ndiff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c\nindex 8c7a83f578..3375392f6c 100644\n--- a/t/helper/test-read-graph.c\n+++ b/t/helper/test-read-graph.c\n@@ -5,20 +5,8 @@\n #include \"bloom.h\"\n #include \"setup.h\"\n \n-int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n+static void dump_graph_info(struct commit_graph *graph)\n {\n-\tstruct commit_graph *graph = NULL;\n-\tstruct object_directory *odb;\n-\n-\tsetup_git_directory();\n-\todb = the_repository->objects->odb;\n-\n-\tprepare_repo_settings(the_repository);\n-\n-\tgraph = read_commit_graph_one(the_repository, odb);\n-\tif (!graph)\n-\t\treturn 1;\n-\n \tprintf(\"header: %08x %d %d %d %d\\n\",\n \t\tntohl(*(uint32_t*)graph->data),\n \t\t*(unsigned char*)(graph->data + 4),\n@@ -57,6 +45,23 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n \tif (graph->topo_levels)\n \t\tprintf(\" topo_levels\");\n \tprintf(\"\\n\");\n+}\n+\n+int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n+{\n+\tstruct commit_graph *graph = NULL;\n+\tstruct object_directory *odb;\n+\n+\tsetup_git_directory();\n+\todb = the_repository->objects->odb;\n+\n+\tprepare_repo_settings(the_repository);\n+\n+\tgraph = read_commit_graph_one(the_repository, odb);\n+\tif (!graph)\n+\t\treturn 1;\n+\n+\tdump_graph_info(graph);\n \n \tUNLEAK(graph);\n \n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497643","messageId":"ae74fbad3e1b076c97de748f72c61a6521a27391.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 06/16] bloom.h: make `load_bloom_filter_from_graph()` public","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:41Z","receivedAt":"2024-06-25T17:39:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Prepare for a future commit to use the load_bloom_filter_from_graph()\nfunction directly to load specific Bloom filters out of the commit-graph\nfor manual inspection (to be used during tests).\n\nSigned-off-by: Taylor Blau \nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n bloom.c | 6 +++---\n bloom.h | 5 +++++\n 2 files changed, 8 insertions(+), 3 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex e529f7605c..401999ed3c 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -48,9 +48,9 @@ static int check_bloom_offset(struct commit_graph *g, uint32_t pos,\n \treturn -1;\n }\n \n-static int load_bloom_filter_from_graph(struct commit_graph *g,\n-\t\t\t\t\tstruct bloom_filter *filter,\n-\t\t\t\t\tuint32_t graph_pos)\n+int load_bloom_filter_from_graph(struct commit_graph *g,\n+\t\t\t\t struct bloom_filter *filter,\n+\t\t\t\t uint32_t graph_pos)\n {\n \tuint32_t lex_pos, start_index, end_index;\n \ndiff --git a/bloom.h b/bloom.h\nindex adde6dfe21..1e4f612d2c 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -3,6 +3,7 @@\n \n struct commit;\n struct repository;\n+struct commit_graph;\n \n struct bloom_filter_settings {\n \t/*\n@@ -68,6 +69,10 @@ struct bloom_key {\n \tuint32_t *hashes;\n };\n \n+int load_bloom_filter_from_graph(struct commit_graph *g,\n+\t\t\t\t struct bloom_filter *filter,\n+\t\t\t\t uint32_t graph_pos);\n+\n /*\n * Calculate the murmur3 32-bit hash value for the given data\n * using the given seed.\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497644","messageId":"0dfd1a361e93bb4eab672f94f9447b99f63fc4c0.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 07/16] t/helper/test-read-graph: implement `bloom-filters` mode","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:44Z","receivedAt":"2024-06-25T17:39:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Implement a mode of the \"read-graph\" test helper to dump out the\nhexadecimal contents of the Bloom filter(s) contained in a commit-graph.\n\nSigned-off-by: Taylor Blau \nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n t/helper/test-read-graph.c | 44 +++++++++++++++++++++++++++++++++-----\n 1 file changed, 39 insertions(+), 5 deletions(-)\n\ndiff --git a/t/helper/test-read-graph.c b/t/helper/test-read-graph.c\nindex 3375392f6c..da9ac8584d 100644\n--- a/t/helper/test-read-graph.c\n+++ b/t/helper/test-read-graph.c\n@@ -47,10 +47,32 @@ static void dump_graph_info(struct commit_graph *graph)\n \tprintf(\"\\n\");\n }\n \n-int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n+static void dump_graph_bloom_filters(struct commit_graph *graph)\n+{\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < graph->num_commits + graph->num_commits_in_base; i++) {\n+\t\tstruct bloom_filter filter = { 0 };\n+\t\tsize_t j;\n+\n+\t\tif (load_bloom_filter_from_graph(graph, &filter, i) < 0) {\n+\t\t\tfprintf(stderr, \"missing Bloom filter for graph \"\n+\t\t\t\t\"position %\"PRIu32\"\\n\", i);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tfor (j = 0; j < filter.len; j++)\n+\t\t\tprintf(\"%02x\", filter.data[j]);\n+\t\tif (filter.len)\n+\t\t\tprintf(\"\\n\");\n+\t}\n+}\n+\n+int cmd__read_graph(int argc, const char **argv)\n {\n \tstruct commit_graph *graph = NULL;\n \tstruct object_directory *odb;\n+\tint ret = 0;\n \n \tsetup_git_directory();\n \todb = the_repository->objects->odb;\n@@ -58,12 +80,24 @@ int cmd__read_graph(int argc UNUSED, const char **argv UNUSED)\n \tprepare_repo_settings(the_repository);\n \n \tgraph = read_commit_graph_one(the_repository, odb);\n-\tif (!graph)\n-\t\treturn 1;\n+\tif (!graph) {\n+\t\tret = 1;\n+\t\tgoto done;\n+\t}\n \n-\tdump_graph_info(graph);\n+\tif (argc <= 1)\n+\t\tdump_graph_info(graph);\n+\telse if (!strcmp(argv[1], \"bloom-filters\"))\n+\t\tdump_graph_bloom_filters(graph);\n+\telse {\n+\t\tfprintf(stderr, \"unknown sub-command: '%s'\\n\", argv[1]);\n+\t\tret = 1;\n+\t}\n \n+done:\n \tUNLEAK(graph);\n \n-\treturn 0;\n+\treturn ret;\n }\n+\n+\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497645","messageId":"fbcaa686b1088544f22c883fe4437a6645d6619d.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 08/16] t4216: test changed path filters with high bit paths","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:47Z","receivedAt":"2024-06-25T17:39:50Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Subsequent commits will teach Git another version of changed path\nfilter that has different behavior with paths that contain at least\none character with its high bit set, so test the existing behavior as\na baseline.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n t/t4216-log-bloom.sh | 51 ++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 51 insertions(+)\n\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex c1977961d0..49d1113171 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -488,6 +488,57 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '\n \ttest_must_be_empty err\n '\n \n+get_first_changed_path_filter () {\n+\ttest-tool read-graph bloom-filters >filters.dat &&\n+\thead -n 1 filters.dat\n+}\n+\n+# chosen to be the same under all Unicode normalization forms\n+CENT=$(printf \"\\302\\242\")\n+\n+test_expect_success 'set up repo with high bit path, version 1 changed-path' '\n+\tgit init highbit1 &&\n+\ttest_commit -C highbit1 c1 \"$CENT\" &&\n+\tgit -C highbit1 commit-graph write --reachable --changed-paths\n+'\n+\n+test_expect_success 'setup check value of version 1 changed-path' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\techo \"52a9\" >expect &&\n+\t\tget_first_changed_path_filter >actual\n+\t)\n+'\n+\n+# expect will not match actual if char is unsigned by default. Write the test\n+# in this way, so that a user running this test script can still see if the two\n+# files match. (It will appear as an ordinary success if they match, and a skip\n+# if not.)\n+if test_cmp highbit1/expect highbit1/actual\n+then\n+\ttest_set_prereq SIGNED_CHAR_BY_DEFAULT\n+fi\n+test_expect_success SIGNED_CHAR_BY_DEFAULT 'check value of version 1 changed-path' '\n+\t# Only the prereq matters for this test.\n+\ttrue\n+'\n+\n+test_expect_success 'setup make another commit' '\n+\t# \"git log\" does not use Bloom filters for root commits - see how, in\n+\t# revision.c, rev_compare_tree() (the only code path that eventually calls\n+\t# get_bloom_filter()) is only called by try_to_simplify_commit() when the commit\n+\t# has one parent. Therefore, make another commit so that we perform the tests on\n+\t# a non-root commit.\n+\ttest_commit -C highbit1 anotherc1 \"another$CENT\"\n+'\n+\n+test_expect_success 'version 1 changed-path used when version 1 requested' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n corrupt_graph () {\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497646","messageId":"60c063ca4aa86e0397b42f2c742f986987490683.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 09/16] repo-settings: introduce commitgraph.changedPathsVersion","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:50Z","receivedAt":"2024-06-25T17:39:53Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"A subsequent commit will introduce another version of the changed-path\nfilter in the commit graph file. In order to control which version to\nwrite (and read), a config variable is needed.\n\nTherefore, introduce this config variable. For forwards compatibility,\nteach Git to not read commit graphs when the config variable\nis set to an unsupported version. Because we teach Git this,\ncommitgraph.readChangedPaths is now redundant, so deprecate it and\ndefine its behavior in terms of the config variable we introduce.\n\nThis commit does not change the behavior of writing (Git writes changed\npath filters when explicitly instructed regardless of any config\nvariable), but a subsequent commit will restrict Git such that it will\nonly write when commitgraph.changedPathsVersion is a recognized value.\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n Documentation/config/commitgraph.txt | 26 +++++++++++++++++++++++---\n commit-graph.c | 5 +++--\n oss-fuzz/fuzz-commit-graph.c | 2 +-\n repo-settings.c | 6 +++++-\n repository.h | 2 +-\n 5 files changed, 33 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt\nindex 30604e4a4c..e68cdededa 100644\n--- a/Documentation/config/commitgraph.txt\n+++ b/Documentation/config/commitgraph.txt\n@@ -9,6 +9,26 @@ commitGraph.maxNewFilters::\n \tcommit-graph write` (c.f., linkgit:git-commit-graph[1]).\n \n commitGraph.readChangedPaths::\n-\tIf true, then git will use the changed-path Bloom filters in the\n-\tcommit-graph file (if it exists, and they are present). Defaults to\n-\ttrue. See linkgit:git-commit-graph[1] for more information.\n+\tDeprecated. Equivalent to commitGraph.changedPathsVersion=-1 if true, and\n+\tcommitGraph.changedPathsVersion=0 if false. (If commitGraph.changedPathVersion\n+\tis also set, commitGraph.changedPathsVersion takes precedence.)\n+\n+commitGraph.changedPathsVersion::\n+\tSpecifies the version of the changed-path Bloom filters that Git will read and\n+\twrite. May be -1, 0 or 1. Note that values greater than 1 may be\n+\tincompatible with older versions of Git which do not yet understand\n+\tthose versions. Use caution when operating in a mixed-version\n+\tenvironment.\n++\n+Defaults to -1.\n++\n+If -1, Git will use the version of the changed-path Bloom filters in the\n+repository, defaulting to 1 if there are none.\n++\n+If 0, Git will not read any Bloom filters, and will write version 1 Bloom\n+filters when instructed to write.\n++\n+If 1, Git will only read version 1 Bloom filters, and will write version 1\n+Bloom filters.\n++\n+See linkgit:git-commit-graph[1] for more information.\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 3d89febae4..87b07e7b85 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -459,7 +459,7 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,\n \t\t\tgraph->read_generation_data = 1;\n \t}\n \n-\tif (s->commit_graph_read_changed_paths) {\n+\tif (s->commit_graph_changed_paths_version) {\n \t\tread_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,\n \t\t\t graph_read_bloom_index, graph);\n \t\tread_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,\n@@ -555,7 +555,8 @@ static void validate_mixed_bloom_settings(struct commit_graph *g)\n \t\t}\n \n \t\tif (g->bloom_filter_settings->bits_per_entry != settings->bits_per_entry ||\n-\t\t g->bloom_filter_settings->num_hashes != settings->num_hashes) {\n+\t\t g->bloom_filter_settings->num_hashes != settings->num_hashes ||\n+\t\t g->bloom_filter_settings->hash_version != settings->hash_version) {\n \t\t\tg->chunk_bloom_indexes = NULL;\n \t\t\tg->chunk_bloom_data = NULL;\n \t\t\tFREE_AND_NULL(g->bloom_filter_settings);\ndiff --git a/oss-fuzz/fuzz-commit-graph.c b/oss-fuzz/fuzz-commit-graph.c\nindex 75e668a057..c4e555fbe3 100644\n--- a/oss-fuzz/fuzz-commit-graph.c\n+++ b/oss-fuzz/fuzz-commit-graph.c\n@@ -21,7 +21,7 @@ int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)\n \t */\n \trepo_set_hash_algo(the_repository, GIT_HASH_SHA1);\n \tthe_repository->settings.commit_graph_generation_version = 2;\n-\tthe_repository->settings.commit_graph_read_changed_paths = 1;\n+\tthe_repository->settings.commit_graph_changed_paths_version = 1;\n \tg = parse_commit_graph(&the_repository->settings, (void *)data, size);\n \trepo_clear(the_repository);\n \tfree_commit_graph(g);\ndiff --git a/repo-settings.c b/repo-settings.c\nindex a0b590bc6c..2b4e68731b 100644\n--- a/repo-settings.c\n+++ b/repo-settings.c\n@@ -23,6 +23,7 @@ void prepare_repo_settings(struct repository *r)\n \tint value;\n \tconst char *strval;\n \tint manyfiles;\n+\tint read_changed_paths;\n \n \tif (!r->gitdir)\n \t\tBUG(\"Cannot add settings for uninitialized repository\");\n@@ -54,7 +55,10 @@ void prepare_repo_settings(struct repository *r)\n \t/* Commit graph config or default, does not cascade (simple) */\n \trepo_cfg_bool(r, \"core.commitgraph\", &r->settings.core_commit_graph, 1);\n \trepo_cfg_int(r, \"commitgraph.generationversion\", &r->settings.commit_graph_generation_version, 2);\n-\trepo_cfg_bool(r, \"commitgraph.readchangedpaths\", &r->settings.commit_graph_read_changed_paths, 1);\n+\trepo_cfg_bool(r, \"commitgraph.readchangedpaths\", &read_changed_paths, 1);\n+\trepo_cfg_int(r, \"commitgraph.changedpathsversion\",\n+\t\t &r->settings.commit_graph_changed_paths_version,\n+\t\t read_changed_paths ? -1 : 0);\n \trepo_cfg_bool(r, \"gc.writecommitgraph\", &r->settings.gc_write_commit_graph, 1);\n \trepo_cfg_bool(r, \"fetch.writecommitgraph\", &r->settings.fetch_write_commit_graph, 0);\n \ndiff --git a/repository.h b/repository.h\nindex a35cd77c35..bd7a408013 100644\n--- a/repository.h\n+++ b/repository.h\n@@ -32,7 +32,7 @@ struct repo_settings {\n \n \tint core_commit_graph;\n \tint commit_graph_generation_version;\n-\tint commit_graph_read_changed_paths;\n+\tint commit_graph_changed_paths_version;\n \tint gc_write_commit_graph;\n \tint fetch_write_commit_graph;\n \tint command_requires_full_index;\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497647","messageId":"ce3a15a517aa74c77e68096499368a2dc9e5587d.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 10/16] bloom: annotate filters with hash version","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:54Z","receivedAt":"2024-06-25T17:39:58Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In subsequent commits, we will want to load existing Bloom filters out\nof a commit-graph, even when the hash version they were computed with\ndoes not match the value of `commitGraph.changedPathVersion`.\n\nIn order to differentiate between the two, add a \"version\" field to each\nBloom filter.\n\nSigned-off-by: Taylor Blau \n---\n bloom.c | 11 ++++++++---\n bloom.h | 1 +\n 2 files changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 401999ed3c..e64e53bc4c 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -88,6 +88,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n \tfilter->data = (unsigned char *)(g->chunk_bloom_data +\n \t\t\t\t\tsizeof(unsigned char) * start_index +\n \t\t\t\t\tBLOOMDATA_CHUNK_HEADER_SIZE);\n+\tfilter->version = g->bloom_filter_settings->hash_version;\n \n \treturn 1;\n }\n@@ -210,11 +211,13 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,\n \treturn strcmp(e1->path, e2->path);\n }\n \n-static void init_truncated_large_filter(struct bloom_filter *filter)\n+static void init_truncated_large_filter(struct bloom_filter *filter,\n+\t\t\t\t\tint version)\n {\n \tfilter->data = xmalloc(1);\n \tfilter->data[0] = 0xFF;\n \tfilter->len = 1;\n+\tfilter->version = version;\n }\n \n struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n@@ -299,13 +302,15 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t}\n \n \t\tif (hashmap_get_size(&pathmap) > settings->max_changed_paths) {\n-\t\t\tinit_truncated_large_filter(filter);\n+\t\t\tinit_truncated_large_filter(filter,\n+\t\t\t\t\t\t settings->hash_version);\n \t\t\tif (computed)\n \t\t\t\t*computed |= BLOOM_TRUNC_LARGE;\n \t\t\tgoto cleanup;\n \t\t}\n \n \t\tfilter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;\n+\t\tfilter->version = settings->hash_version;\n \t\tif (!filter->len) {\n \t\t\tif (computed)\n \t\t\t\t*computed |= BLOOM_TRUNC_EMPTY;\n@@ -325,7 +330,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t} else {\n \t\tfor (i = 0; i < diff_queued_diff.nr; i++)\n \t\t\tdiff_free_filepair(diff_queued_diff.queue[i]);\n-\t\tinit_truncated_large_filter(filter);\n+\t\tinit_truncated_large_filter(filter, settings->hash_version);\n \n \t\tif (computed)\n \t\t\t*computed |= BLOOM_TRUNC_LARGE;\ndiff --git a/bloom.h b/bloom.h\nindex 1e4f612d2c..c9dd7d4022 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -53,6 +53,7 @@ struct bloom_filter_settings {\n struct bloom_filter {\n \tunsigned char *data;\n \tsize_t len;\n+\tint version;\n };\n \n /*\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497648","messageId":"99ab9cf448eea65db1a561a79223fe70073d1be0.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 11/16] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:39:57Z","receivedAt":"2024-06-25T17:40:00Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Callers use the inline `get_bloom_filter()` implementation as a thin\nwrapper around `get_or_compute_bloom_filter()`. The former calls the\nlatter with a value of \"0\" for `compute_if_not_present`, making\n`get_bloom_filter()` the default read-only path for fetching an existing\nBloom filter.\n\nCallers expect the value returned from `get_bloom_filter()` is usable,\nthat is that it's compatible with the configured value corresponding to\n`commitGraph.changedPathsVersion`.\n\nThis is OK, since the commit-graph machinery only initializes its BDAT\nchunk (thereby enabling it to service Bloom filter queries) when the\nBloom filter hash_version is compatible with our settings. So any value\nreturned by `get_bloom_filter()` is trivially useable.\n\nHowever, subsequent commits will load the BDAT chunk even when the Bloom\nfilters are built with incompatible hash versions. Prepare to handle\nthis by teaching `get_bloom_filter()` to discard filters that are\nincompatible with the configured hash version.\n\nCallers who wish to read incompatible filters (e.g., for upgrading\nfilters from v1 to v2) may use the lower level routine,\n`get_or_compute_bloom_filter()`.\n\nSigned-off-by: Taylor Blau \n---\n bloom.c | 20 +++++++++++++++++++-\n bloom.h | 20 ++++++++++++++++++--\n 2 files changed, 37 insertions(+), 3 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex e64e53bc4c..c24489dbcf 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -220,6 +220,23 @@ static void init_truncated_large_filter(struct bloom_filter *filter,\n \tfilter->version = version;\n }\n \n+struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n+{\n+\tstruct bloom_filter *filter;\n+\tint hash_version;\n+\n+\tfilter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL);\n+\tif (!filter)\n+\t\treturn NULL;\n+\n+\tprepare_repo_settings(r);\n+\thash_version = r->settings.commit_graph_changed_paths_version;\n+\n+\tif (!(hash_version == -1 || hash_version == filter->version))\n+\t\treturn NULL; /* unusable filter */\n+\treturn filter;\n+}\n+\n struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t struct commit *c,\n \t\t\t\t\t\t int compute_if_not_present,\n@@ -245,7 +262,8 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t filter, graph_pos);\n \t}\n \n-\tif (filter->data && filter->len)\n+\tif ((filter->data && filter->len) &&\n+\t (!settings || settings->hash_version == filter->version))\n \t\treturn filter;\n \tif (!compute_if_not_present)\n \t\treturn NULL;\ndiff --git a/bloom.h b/bloom.h\nindex c9dd7d4022..052a993aab 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -108,8 +108,24 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t const struct bloom_filter_settings *settings,\n \t\t\t\t\t\t enum bloom_filter_computed *computed);\n \n-#define get_bloom_filter(r, c) get_or_compute_bloom_filter( \\\n-\t(r), (c), 0, NULL, NULL)\n+/*\n+ * Find the Bloom filter associated with the given commit \"c\".\n+ *\n+ * If any of the following are true\n+ *\n+ * - the repository does not have a commit-graph, or\n+ * - the repository disables reading from the commit-graph, or\n+ * - the given commit does not have a Bloom filter computed, or\n+ * - there is a Bloom filter for commit \"c\", but it cannot be read\n+ * because the filter uses an incompatible version of murmur3\n+ *\n+ * , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding\n+ * Bloom filter will be returned.\n+ *\n+ * For callers who wish to inspect Bloom filters with incompatible hash\n+ * versions, use get_or_compute_bloom_filter().\n+ */\n+struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c);\n \n int bloom_filter_contains(const struct bloom_filter *filter,\n \t\t\t const struct bloom_key *key,\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497649","messageId":"99e66d1dba5c4d7d57859ba5f6ef9e0d349dd356.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 12/16] commit-graph: unconditionally load Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:40:00Z","receivedAt":"2024-06-25T17:40:03Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In an earlier commit, we began ignoring the Bloom data (\"BDAT\") chunk\nfor commit-graphs whose Bloom filters were computed using a hash version\nincompatible with the value of `commitGraph.changedPathVersion`.\n\nNow that the Bloom API has been hardened to discard these incompatible\nfilters (with the exception of low-level APIs), we can safely load these\nBloom filters unconditionally.\n\nWe no longer want to return early from `graph_read_bloom_data()`, and\nsimilarly do not want to set the bloom_settings' `hash_version` field as\na side-effect. The latter is because we want to wait until we know which\nBloom settings we're using (either the defaults, from the GIT_TEST\nvariables, or from the previous commit-graph layer) before deciding what\nhash_version to use.\n\nIf we detect an existing BDAT chunk, we'll infer the rest of the\nsettings (e.g., number of hashes, bits per entry, and maximum number of\nchanged paths) from the earlier graph layer. The hash_version will be\ninferred from the previous layer as well, unless one has already been\nspecified via configuration.\n\nOnce all of that is done, we normalize the value of the hash_version to\neither \"1\" or \"2\".\n\nSigned-off-by: Taylor Blau \n---\n commit-graph.c | 14 ++++++++++----\n 1 file changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 87b07e7b85..8129a4f5dc 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -358,9 +358,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \tg->chunk_bloom_data_size = chunk_size;\n \thash_version = get_be32(chunk_start);\n \n-\tif (hash_version != 1)\n-\t\treturn 0;\n-\n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n \tg->bloom_filter_settings->hash_version = hash_version;\n \tg->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);\n@@ -2514,6 +2511,7 @@ int write_commit_graph(struct object_directory *odb,\n \tctx->write_generation_data = (get_configured_generation_version(r) == 2);\n \tctx->num_generation_data_overflows = 0;\n \n+\tbloom_settings.hash_version = r->settings.commit_graph_changed_paths_version;\n \tbloom_settings.bits_per_entry = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY\",\n \t\t\t\t\t\t bloom_settings.bits_per_entry);\n \tbloom_settings.num_hashes = git_env_ulong(\"GIT_TEST_BLOOM_SETTINGS_NUM_HASHES\",\n@@ -2545,10 +2543,18 @@ int write_commit_graph(struct object_directory *odb,\n \t\t/* We have changed-paths already. Keep them in the next graph */\n \t\tif (g && g->chunk_bloom_data) {\n \t\t\tctx->changed_paths = 1;\n-\t\t\tctx->bloom_settings = g->bloom_filter_settings;\n+\n+\t\t\t/* don't propagate the hash_version unless unspecified */\n+\t\t\tif (bloom_settings.hash_version == -1)\n+\t\t\t\tbloom_settings.hash_version = g->bloom_filter_settings->hash_version;\n+\t\t\tbloom_settings.bits_per_entry = g->bloom_filter_settings->bits_per_entry;\n+\t\t\tbloom_settings.num_hashes = g->bloom_filter_settings->num_hashes;\n+\t\t\tbloom_settings.max_changed_paths = g->bloom_filter_settings->max_changed_paths;\n \t\t}\n \t}\n \n+\tbloom_settings.hash_version = bloom_settings.hash_version == 2 ? 2 : 1;\n+\n \tif (ctx->split) {\n \t\tstruct commit_graph *g = ctx->r->objects->commit_graph;\n \n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497650","messageId":"2e945c3d2e3ac6b5cb3e56689691b6f251a77262.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 13/16] commit-graph: new Bloom filter version that fixes murmur3","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:40:04Z","receivedAt":"2024-06-25T17:40:07Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"The murmur3 implementation in bloom.c has a bug when converting series\nof 4 bytes into network-order integers when char is signed (which is\ncontrollable by a compiler option, and the default signedness of char is\nplatform-specific). When a string contains characters with the high bit\nset, this bug causes results that, although internally consistent within\nGit, does not accord with other implementations of murmur3 (thus,\nthe changed path filters wouldn't be readable by other off-the-shelf\nimplementatios of murmur3) and even with Git binaries that were compiled\nwith different signedness of char. This bug affects both how Git writes\nchanged path filters to disk and how Git interprets changed path filters\non disk.\n\nTherefore, introduce a new version (2) of changed path filters that\ncorrects this problem. The existing version (1) is still supported and\nis still the default, but users should migrate away from it as soon\nas possible.\n\nBecause this bug only manifests with characters that have the high bit\nset, it may be possible that some (or all) commits in a given repo would\nhave the same changed path filter both before and after this fix is\napplied. However, in order to determine whether this is the case, the\nchanged paths would first have to be computed, at which point it is not\nmuch more expensive to just compute a new changed path filter.\n\nSo this patch does not include any mechanism to \"salvage\" changed path\nfilters from repositories. There is also no \"mixed\" mode - for each\ninvocation of Git, reading and writing changed path filters are done\nwith the same version number; this version number may be explicitly\nstated (typically if the user knows which version they need) or\nautomatically determined from the version of the existing changed path\nfilters in the repository.\n\nThere is a change in write_commit_graph(). graph_read_bloom_data()\nmakes it possible for chunk_bloom_data to be non-NULL but\nbloom_filter_settings to be NULL, which causes a segfault later on. I\nproduced such a segfault while developing this patch, but couldn't find\na way to reproduce it neither after this complete patch (or before),\nbut in any case it seemed like a good thing to include that might help\nfuture patch authors.\n\nThe value in t0095 was obtained from another murmur3 implementation\nusing the following Go source code:\n\n package main\n\n import \"fmt\"\n import \"github.com/spaolacci/murmur3\"\n\n func main() {\n fmt.Printf(\"%x\\n\", murmur3.Sum32([]byte(\"Hello world!\")))\n fmt.Printf(\"%x\\n\", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff}))\n }\n\nSigned-off-by: Jonathan Tan \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n Documentation/config/commitgraph.txt | 5 +-\n bloom.c | 69 +++++++++++-\n bloom.h | 8 +-\n commit-graph.c | 13 ++-\n t/helper/test-bloom.c | 9 +-\n t/t0095-bloom.sh | 8 ++\n t/t4216-log-bloom.sh | 155 ++++++++++++++++++++++++++-\n 7 files changed, 252 insertions(+), 15 deletions(-)\n\ndiff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt\nindex e68cdededa..7f8c9d6638 100644\n--- a/Documentation/config/commitgraph.txt\n+++ b/Documentation/config/commitgraph.txt\n@@ -15,7 +15,7 @@ commitGraph.readChangedPaths::\n \n commitGraph.changedPathsVersion::\n \tSpecifies the version of the changed-path Bloom filters that Git will read and\n-\twrite. May be -1, 0 or 1. Note that values greater than 1 may be\n+\twrite. May be -1, 0, 1, or 2. Note that values greater than 1 may be\n \tincompatible with older versions of Git which do not yet understand\n \tthose versions. Use caution when operating in a mixed-version\n \tenvironment.\n@@ -31,4 +31,7 @@ filters when instructed to write.\n If 1, Git will only read version 1 Bloom filters, and will write version 1\n Bloom filters.\n +\n+If 2, Git will only read version 2 Bloom filters, and will write version 2\n+Bloom filters.\n++\n See linkgit:git-commit-graph[1] for more information.\ndiff --git a/bloom.c b/bloom.c\nindex c24489dbcf..323d8012b8 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -100,7 +100,64 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n * Not considered to be cryptographically secure.\n * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm\n */\n-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)\n+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)\n+{\n+\tconst uint32_t c1 = 0xcc9e2d51;\n+\tconst uint32_t c2 = 0x1b873593;\n+\tconst uint32_t r1 = 15;\n+\tconst uint32_t r2 = 13;\n+\tconst uint32_t m = 5;\n+\tconst uint32_t n = 0xe6546b64;\n+\tint i;\n+\tuint32_t k1 = 0;\n+\tconst char *tail;\n+\n+\tint len4 = len / sizeof(uint32_t);\n+\n+\tuint32_t k;\n+\tfor (i = 0; i < len4; i++) {\n+\t\tuint32_t byte1 = (uint32_t)(unsigned char)data[4*i];\n+\t\tuint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8;\n+\t\tuint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16;\n+\t\tuint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24;\n+\t\tk = byte1 | byte2 | byte3 | byte4;\n+\t\tk *= c1;\n+\t\tk = rotate_left(k, r1);\n+\t\tk *= c2;\n+\n+\t\tseed ^= k;\n+\t\tseed = rotate_left(seed, r2) * m + n;\n+\t}\n+\n+\ttail = (data + len4 * sizeof(uint32_t));\n+\n+\tswitch (len & (sizeof(uint32_t) - 1)) {\n+\tcase 3:\n+\t\tk1 ^= ((uint32_t)(unsigned char)tail[2]) << 16;\n+\t\t/*-fallthrough*/\n+\tcase 2:\n+\t\tk1 ^= ((uint32_t)(unsigned char)tail[1]) << 8;\n+\t\t/*-fallthrough*/\n+\tcase 1:\n+\t\tk1 ^= ((uint32_t)(unsigned char)tail[0]) << 0;\n+\t\tk1 *= c1;\n+\t\tk1 = rotate_left(k1, r1);\n+\t\tk1 *= c2;\n+\t\tseed ^= k1;\n+\t\tbreak;\n+\t}\n+\n+\tseed ^= (uint32_t)len;\n+\tseed ^= (seed >> 16);\n+\tseed *= 0x85ebca6b;\n+\tseed ^= (seed >> 13);\n+\tseed *= 0xc2b2ae35;\n+\tseed ^= (seed >> 16);\n+\n+\treturn seed;\n+}\n+\n+static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)\n {\n \tconst uint32_t c1 = 0xcc9e2d51;\n \tconst uint32_t c2 = 0x1b873593;\n@@ -165,8 +222,14 @@ void fill_bloom_key(const char *data,\n \tint i;\n \tconst uint32_t seed0 = 0x293ae76f;\n \tconst uint32_t seed1 = 0x7e646e2c;\n-\tconst uint32_t hash0 = murmur3_seeded(seed0, data, len);\n-\tconst uint32_t hash1 = murmur3_seeded(seed1, data, len);\n+\tuint32_t hash0, hash1;\n+\tif (settings->hash_version == 2) {\n+\t\thash0 = murmur3_seeded_v2(seed0, data, len);\n+\t\thash1 = murmur3_seeded_v2(seed1, data, len);\n+\t} else {\n+\t\thash0 = murmur3_seeded_v1(seed0, data, len);\n+\t\thash1 = murmur3_seeded_v1(seed1, data, len);\n+\t}\n \n \tkey->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));\n \tfor (i = 0; i < settings->num_hashes; i++)\ndiff --git a/bloom.h b/bloom.h\nindex 052a993aab..bfe389e29c 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -8,9 +8,11 @@ struct commit_graph;\n struct bloom_filter_settings {\n \t/*\n \t * The version of the hashing technique being used.\n-\t * We currently only support version = 1 which is\n+\t * The newest version is 2, which is\n \t * the seeded murmur3 hashing technique implemented\n-\t * in bloom.c.\n+\t * in bloom.c. Bloom filters of version 1 were created\n+\t * with prior versions of Git, which had a bug in the\n+\t * implementation of the hash function.\n \t */\n \tuint32_t hash_version;\n \n@@ -81,7 +83,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n * Not considered to be cryptographically secure.\n * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm\n */\n-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);\n+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len);\n \n void fill_bloom_key(const char *data,\n \t\t size_t len,\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 8129a4f5dc..c1177631bb 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -344,7 +344,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \t\t\t\t size_t chunk_size, void *data)\n {\n \tstruct commit_graph *g = data;\n-\tuint32_t hash_version;\n \n \tif (chunk_size < BLOOMDATA_CHUNK_HEADER_SIZE) {\n \t\twarning(_(\"ignoring too-small changed-path chunk\"\n@@ -356,10 +355,9 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \n \tg->chunk_bloom_data = chunk_start;\n \tg->chunk_bloom_data_size = chunk_size;\n-\thash_version = get_be32(chunk_start);\n \n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n-\tg->bloom_filter_settings->hash_version = hash_version;\n+\tg->bloom_filter_settings->hash_version = get_be32(chunk_start);\n \tg->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);\n \tg->bloom_filter_settings->bits_per_entry = get_be32(chunk_start + 8);\n \tg->bloom_filter_settings->max_changed_paths = DEFAULT_BLOOM_MAX_CHANGES;\n@@ -2499,6 +2497,13 @@ int write_commit_graph(struct object_directory *odb,\n \t}\n \tif (!commit_graph_compatible(r))\n \t\treturn 0;\n+\tif (r->settings.commit_graph_changed_paths_version < -1\n+\t || r->settings.commit_graph_changed_paths_version > 2) {\n+\t\twarning(_(\"attempting to write a commit-graph, but \"\n+\t\t\t \"'commitGraph.changedPathsVersion' (%d) is not supported\"),\n+\t\t\tr->settings.commit_graph_changed_paths_version);\n+\t\treturn 0;\n+\t}\n \n \tCALLOC_ARRAY(ctx, 1);\n \tctx->r = r;\n@@ -2541,7 +2546,7 @@ int write_commit_graph(struct object_directory *odb,\n \t\tg = ctx->r->objects->commit_graph;\n \n \t\t/* We have changed-paths already. Keep them in the next graph */\n-\t\tif (g && g->chunk_bloom_data) {\n+\t\tif (g && g->bloom_filter_settings) {\n \t\t\tctx->changed_paths = 1;\n \n \t\t\t/* don't propagate the hash_version unless unspecified */\ndiff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\nindex 1281e66876..eefc1668c7 100644\n--- a/t/helper/test-bloom.c\n+++ b/t/helper/test-bloom.c\n@@ -49,6 +49,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)\n \n static const char *bloom_usage = \"\\n\"\n \" test-tool bloom get_murmur3 \\n\"\n+\" test-tool bloom get_murmur3_seven_highbit\\n\"\n \" test-tool bloom generate_filter [...]\\n\"\n \" test-tool bloom get_filter_for_commit \\n\";\n \n@@ -63,7 +64,13 @@ int cmd__bloom(int argc, const char **argv)\n \t\tuint32_t hashed;\n \t\tif (argc < 3)\n \t\t\tusage(bloom_usage);\n-\t\thashed = murmur3_seeded(0, argv[2], strlen(argv[2]));\n+\t\thashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2]));\n+\t\tprintf(\"Murmur3 Hash with seed=0:0x%08x\\n\", hashed);\n+\t}\n+\n+\tif (!strcmp(argv[1], \"get_murmur3_seven_highbit\")) {\n+\t\tuint32_t hashed;\n+\t\thashed = murmur3_seeded_v2(0, \"\\x99\\xaa\\xbb\\xcc\\xdd\\xee\\xff\", 7);\n \t\tprintf(\"Murmur3 Hash with seed=0:0x%08x\\n\", hashed);\n \t}\n \ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex b567383eb8..c8d84ab606 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -29,6 +29,14 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'compute unseeded murmur3 hash for test string 3' '\n+\tcat >expect <<-\\EOF &&\n+\tMurmur3 Hash with seed=0:0xa183ccfd\n+\tEOF\n+\ttest-tool bloom get_murmur3_seven_highbit >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'compute bloom key for empty string' '\n \tcat >expect <<-\\EOF &&\n \tHashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex 49d1113171..cc6e5733f6 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -488,14 +488,49 @@ test_expect_success 'merge graph layers with incompatible Bloom settings' '\n \ttest_must_be_empty err\n '\n \n+# chosen to be the same under all Unicode normalization forms\n+CENT=$(printf \"\\302\\242\")\n+\n+test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '\n+\trm \"$repo/$graph\" &&\n+\n+\tgit -C $repo log --oneline --no-decorate -- $CENT >expect &&\n+\n+\t# Compute v1 Bloom filters for commits at the bottom.\n+\tgit -C $repo rev-parse HEAD^ >in &&\n+\tgit -C $repo commit-graph write --stdin-commits --changed-paths \\\n+\t\t--split in &&\n+\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write \\\n+\t\t--stdin-commits --changed-paths --split=no-merge actual 2>err &&\n+\ttest_cmp expect actual &&\n+\n+\tlayer=\"$(head -n 1 $repo/$chain)\" &&\n+\tcat >expect.err <<-EOF &&\n+\twarning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings\n+\tEOF\n+\ttest_cmp expect.err err &&\n+\n+\t# Merge the two layers with incompatible bloom filter versions,\n+\t# ensuring that the v2 filters are used.\n+\t>trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write --reachable --changed-paths 2>err &&\n+\tgrep \"disabling Bloom filters for commit-graph layer .$layer.\" err &&\n+\tgrep \"{\\\"hash_version\\\":2,\\\"num_hashes\\\":7,\\\"bits_per_entry\\\":10,\\\"max_changed_paths\\\":512\" trace2.txt\n+'\n+\n get_first_changed_path_filter () {\n \ttest-tool read-graph bloom-filters >filters.dat &&\n \thead -n 1 filters.dat\n }\n \n-# chosen to be the same under all Unicode normalization forms\n-CENT=$(printf \"\\302\\242\")\n-\n test_expect_success 'set up repo with high bit path, version 1 changed-path' '\n \tgit init highbit1 &&\n \ttest_commit -C highbit1 c1 \"$CENT\" &&\n@@ -539,6 +574,120 @@ test_expect_success 'version 1 changed-path used when version 1 requested' '\n \t)\n '\n \n+test_expect_success 'version 1 changed-path not used when version 2 requested' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\tgit config --add commitGraph.changedPathsVersion 2 &&\n+\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'version 1 changed-path used when autodetect requested' '\n+\t(\n+\t\tcd highbit1 &&\n+\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '\n+\ttest_commit -C highbit1 c1double \"$CENT$CENT\" &&\n+\tgit -C highbit1 commit-graph write --reachable --changed-paths &&\n+\t(\n+\t\tcd highbit1 &&\n+\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n+\t\techo \"options: bloom(1,10,7) read_generation_data\" >expect &&\n+\t\ttest-tool read-graph >full &&\n+\t\tgrep options full >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'set up repo with high bit path, version 2 changed-path' '\n+\tgit init highbit2 &&\n+\tgit -C highbit2 config --add commitGraph.changedPathsVersion 2 &&\n+\ttest_commit -C highbit2 c2 \"$CENT\" &&\n+\tgit -C highbit2 commit-graph write --reachable --changed-paths\n+'\n+\n+test_expect_success 'check value of version 2 changed-path' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\techo \"c01f\" >expect &&\n+\t\tget_first_changed_path_filter >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'setup make another commit' '\n+\t# \"git log\" does not use Bloom filters for root commits - see how, in\n+\t# revision.c, rev_compare_tree() (the only code path that eventually calls\n+\t# get_bloom_filter()) is only called by try_to_simplify_commit() when the commit\n+\t# has one parent. Therefore, make another commit so that we perform the tests on\n+\t# a non-root commit.\n+\ttest_commit -C highbit2 anotherc2 \"another$CENT\"\n+'\n+\n+test_expect_success 'version 2 changed-path used when version 2 requested' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'version 2 changed-path not used when version 1 requested' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\tgit config --add commitGraph.changedPathsVersion 1 &&\n+\t\ttest_bloom_filters_not_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'version 2 changed-path used when autodetect requested' '\n+\t(\n+\t\tcd highbit2 &&\n+\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n+\t\ttest_bloom_filters_used \"-- another$CENT\"\n+\t)\n+'\n+\n+test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' '\n+\ttest_commit -C highbit2 c2double \"$CENT$CENT\" &&\n+\tgit -C highbit2 commit-graph write --reachable --changed-paths &&\n+\t(\n+\t\tcd highbit2 &&\n+\t\tgit config --add commitGraph.changedPathsVersion -1 &&\n+\t\techo \"options: bloom(2,10,7) read_generation_data\" >expect &&\n+\t\ttest-tool read-graph >full &&\n+\t\tgrep options full >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n+test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '\n+\tgit init doublewrite &&\n+\ttest_commit -C doublewrite c \"$CENT\" &&\n+\tgit -C doublewrite config --add commitGraph.changedPathsVersion 1 &&\n+\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\tfor v in -2 3\n+\tdo\n+\t\tgit -C doublewrite config --add commitGraph.changedPathsVersion $v &&\n+\t\tgit -C doublewrite commit-graph write --reachable --changed-paths 2>err &&\n+\t\tcat >expect <<-EOF &&\n+\t\twarning: attempting to write a commit-graph, but ${SQ}commitGraph.changedPathsVersion${SQ} ($v) is not supported\n+\t\tEOF\n+\t\ttest_cmp expect err || return 1\n+\tdone &&\n+\tgit -C doublewrite config --add commitGraph.changedPathsVersion 2 &&\n+\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\t(\n+\t\tcd doublewrite &&\n+\t\techo \"c01f\" >expect &&\n+\t\tget_first_changed_path_filter >actual &&\n+\t\ttest_cmp expect actual\n+\t)\n+'\n+\n corrupt_graph () {\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497651","messageId":"242f023135cfc2301576786172639cc5664d3449.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 14/16] object.h: fix mis-aligned flag bits table","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:40:07Z","receivedAt":"2024-06-25T17:40:11Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Bit position 23 is one column too far to the left.\n\nSigned-off-by: Taylor Blau \n---\n object.h | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/object.h b/object.h\nindex 669b6a18fa..d2f9de6bb5 100644\n--- a/object.h\n+++ b/object.h\n@@ -62,7 +62,7 @@ void object_array_init(struct object_array *array);\n \n /*\n * object flag allocation:\n- * revision.h: 0---------10 15 23------27\n+ * revision.h: 0---------10 15 23------27\n * fetch-pack.c: 01 67\n * negotiator/default.c: 2--5\n * walker.c: 0-2\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497652","messageId":"1b80023e57cc61e6d7f9bffbc0426c703ddce31a.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 15/16] commit-graph: reuse existing Bloom filters where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:40:11Z","receivedAt":"2024-06-25T17:40:14Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In an earlier commit, a bug was described where it's possible for Git to\nproduce non-murmur3 hashes when the platform's \"char\" type is signed,\nand there are paths with characters whose highest bit is set (i.e. all\ncharacters >= 0x80).\n\nThat patch allows the caller to control which version of Bloom filters\nare read and written. However, even on platforms with a signed \"char\"\ntype, it is possible to reuse existing Bloom filters if and only if\nthere are no changed paths in any commit's first parent tree-diff whose\ncharacters have their highest bit set.\n\nWhen this is the case, we can reuse the existing filter without having\nto compute a new one. This is done by marking trees which are known to\nhave (or not have) any such paths. When a commit's root tree is verified\nto not have any such paths, we mark it as such and declare that the\ncommit's Bloom filter is reusable.\n\nNote that this heuristic only goes in one direction. If neither a commit\nnor its first parent have any paths in their trees with non-ASCII\ncharacters, then we know for certain that a path with non-ASCII\ncharacters will not appear in a tree-diff against that commit's first\nparent. The reverse isn't necessarily true: just because the tree-diff\ndoesn't contain any such paths does not imply that no such paths exist\nin either tree.\n\nSo we end up recomputing some Bloom filters that we don't strictly have\nto (i.e. their bits are the same no matter which version of murmur3 we\nuse). But culling these out is impossible, since we'd have to perform\nthe full tree-diff, which is the same effort as computing the Bloom\nfilter from scratch.\n\nBut because we can cache our results in each tree's flag bits, we can\noften avoid recomputing many filters, thereby reducing the time it takes\nto run\n\n $ git commit-graph write --changed-paths --reachable\n\nwhen upgrading from v1 to v2 Bloom filters.\n\nTo benchmark this, let's generate a commit-graph in linux.git with v1\nchanged-paths in generation order[^1]:\n\n $ git clone git@github.com:torvalds/linux.git\n $ cd linux\n $ git commit-graph write --reachable --changed-paths\n $ graph=\".git/objects/info/commit-graph\"\n $ mv $graph{,.bak}\n\nThen let's time how long it takes to go from v1 to v2 filters (with and\nwithout the upgrade path enabled), resetting the state of the\ncommit-graph each time:\n\n $ git config commitGraph.changedPathsVersion 2\n $ hyperfine -p 'cp -f $graph.bak $graph' -L v 0,1 \\\n 'GIT_TEST_UPGRADE_BLOOM_FILTERS={v} git.compile commit-graph write --reachable --changed-paths'\n\nOn linux.git (where there aren't any non-ASCII paths), the timings\nindicate that this patch represents a speed-up over recomputing all\nBloom filters from scratch:\n\n Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths\n Time (mean ± σ): 124.873 s ± 0.316 s [User: 124.081 s, System: 0.643 s]\n Range (min … max): 124.621 s … 125.227 s 3 runs\n\n Benchmark 2: GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths\n Time (mean ± σ): 79.271 s ± 0.163 s [User: 74.611 s, System: 4.521 s]\n Range (min … max): 79.112 s … 79.437 s 3 runs\n\n Summary\n 'GIT_TEST_UPGRADE_BLOOM_FILTERS=1 git.compile commit-graph write --reachable --changed-paths' ran\n 1.58 ± 0.01 times faster than 'GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit-graph write --reachable --changed-paths'\n\nOn git.git, we do have some non-ASCII paths, giving us a more modest\nimprovement from 4.163 seconds to 3.348 seconds, for a 1.24x speed-up.\nOn my machine, the stats for git.git are:\n\n - 8,285 Bloom filters computed from scratch\n - 10 Bloom filters generated as empty\n - 4 Bloom filters generated as truncated due to too many changed paths\n - 65,114 Bloom filters were reused when transitioning from v1 to v2.\n\n[^1]: Note that this is is important, since `--stdin-packs` or\n `--stdin-commits` orders commits in the commit-graph by their pack\n position (with `--stdin-packs`) or in the raw input (with\n `--stdin-commits`).\n\n Since we compute Bloom filters in the same order that commits appear\n in the graph, we must see a commit's (first) parent before we process\n the commit itself. This is only guaranteed to happen when sorting\n commits by their generation number.\n\nSigned-off-by: Taylor Blau \n---\n bloom.c | 90 ++++++++++++++++++++++++++++++++++++++++++--\n bloom.h | 1 +\n commit-graph.c | 5 +++\n object.h | 1 +\n t/t4216-log-bloom.sh | 39 ++++++++++++++++++-\n 5 files changed, 132 insertions(+), 4 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 323d8012b8..740c1767ea 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -6,6 +6,9 @@\n #include \"commit-graph.h\"\n #include \"commit.h\"\n #include \"commit-slab.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+#include \"config.h\"\n \n define_commit_slab(bloom_filter_slab, struct bloom_filter);\n \n@@ -283,6 +286,73 @@ static void init_truncated_large_filter(struct bloom_filter *filter,\n \tfilter->version = version;\n }\n \n+#define VISITED (1u<<21)\n+#define HIGH_BITS (1u<<22)\n+\n+static int has_entries_with_high_bit(struct repository *r, struct tree *t)\n+{\n+\tif (parse_tree(t))\n+\t\treturn 1;\n+\n+\tif (!(t->object.flags & VISITED)) {\n+\t\tstruct tree_desc desc;\n+\t\tstruct name_entry entry;\n+\n+\t\tinit_tree_desc(&desc, &t->object.oid, t->buffer, t->size);\n+\t\twhile (tree_entry(&desc, &entry)) {\n+\t\t\tsize_t i;\n+\t\t\tfor (i = 0; i < entry.pathlen; i++) {\n+\t\t\t\tif (entry.path[i] & 0x80) {\n+\t\t\t\t\tt->object.flags |= HIGH_BITS;\n+\t\t\t\t\tgoto done;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\t\tstruct tree *sub = lookup_tree(r, &entry.oid);\n+\t\t\t\tif (sub && has_entries_with_high_bit(r, sub)) {\n+\t\t\t\t\tt->object.flags |= HIGH_BITS;\n+\t\t\t\t\tgoto done;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t}\n+\n+done:\n+\t\tt->object.flags |= VISITED;\n+\t}\n+\n+\treturn !!(t->object.flags & HIGH_BITS);\n+}\n+\n+static int commit_tree_has_high_bit_paths(struct repository *r,\n+\t\t\t\t\t struct commit *c)\n+{\n+\tstruct tree *t;\n+\tif (repo_parse_commit(r, c))\n+\t\treturn 1;\n+\tt = repo_get_commit_tree(r, c);\n+\tif (!t)\n+\t\treturn 1;\n+\treturn has_entries_with_high_bit(r, t);\n+}\n+\n+static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c,\n+\t\t\t\t\t struct bloom_filter *filter,\n+\t\t\t\t\t int hash_version)\n+{\n+\tstruct commit_list *p = c->parents;\n+\tif (commit_tree_has_high_bit_paths(r, c))\n+\t\treturn NULL;\n+\n+\tif (p && commit_tree_has_high_bit_paths(r, p->item))\n+\t\treturn NULL;\n+\n+\tfilter->version = hash_version;\n+\n+\treturn filter;\n+}\n+\n struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n {\n \tstruct bloom_filter *filter;\n@@ -325,9 +395,23 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\t\t\t\t filter, graph_pos);\n \t}\n \n-\tif ((filter->data && filter->len) &&\n-\t (!settings || settings->hash_version == filter->version))\n-\t\treturn filter;\n+\tif (filter->data && filter->len) {\n+\t\tstruct bloom_filter *upgrade;\n+\t\tif (!settings || settings->hash_version == filter->version)\n+\t\t\treturn filter;\n+\n+\t\t/* version mismatch, see if we can upgrade */\n+\t\tif (compute_if_not_present &&\n+\t\t git_env_bool(\"GIT_TEST_UPGRADE_BLOOM_FILTERS\", 1)) {\n+\t\t\tupgrade = upgrade_filter(r, c, filter,\n+\t\t\t\t\t\t settings->hash_version);\n+\t\t\tif (upgrade) {\n+\t\t\t\tif (computed)\n+\t\t\t\t\t*computed |= BLOOM_UPGRADED;\n+\t\t\t\treturn upgrade;\n+\t\t\t}\n+\t\t}\n+\t}\n \tif (!compute_if_not_present)\n \t\treturn NULL;\n \ndiff --git a/bloom.h b/bloom.h\nindex bfe389e29c..e3a9b68905 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -102,6 +102,7 @@ enum bloom_filter_computed {\n \tBLOOM_COMPUTED = (1 << 1),\n \tBLOOM_TRUNC_LARGE = (1 << 2),\n \tBLOOM_TRUNC_EMPTY = (1 << 3),\n+\tBLOOM_UPGRADED = (1 << 4),\n };\n \n struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\ndiff --git a/commit-graph.c b/commit-graph.c\nindex c1177631bb..2f0a08f302 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1168,6 +1168,7 @@ struct write_commit_graph_context {\n \tint count_bloom_filter_not_computed;\n \tint count_bloom_filter_trunc_empty;\n \tint count_bloom_filter_trunc_large;\n+\tint count_bloom_filter_upgraded;\n };\n \n static int write_graph_chunk_fanout(struct hashfile *f,\n@@ -1775,6 +1776,8 @@ static void trace2_bloom_filter_write_statistics(struct write_commit_graph_conte\n \t\t\t ctx->count_bloom_filter_trunc_empty);\n \ttrace2_data_intmax(\"commit-graph\", ctx->r, \"filter-trunc-large\",\n \t\t\t ctx->count_bloom_filter_trunc_large);\n+\ttrace2_data_intmax(\"commit-graph\", ctx->r, \"filter-upgraded\",\n+\t\t\t ctx->count_bloom_filter_upgraded);\n }\n \n static void compute_bloom_filters(struct write_commit_graph_context *ctx)\n@@ -1816,6 +1819,8 @@ static void compute_bloom_filters(struct write_commit_graph_context *ctx)\n \t\t\t\tctx->count_bloom_filter_trunc_empty++;\n \t\t\tif (computed & BLOOM_TRUNC_LARGE)\n \t\t\t\tctx->count_bloom_filter_trunc_large++;\n+\t\t} else if (computed & BLOOM_UPGRADED) {\n+\t\t\tctx->count_bloom_filter_upgraded++;\n \t\t} else if (computed & BLOOM_NOT_COMPUTED)\n \t\t\tctx->count_bloom_filter_not_computed++;\n \t\tctx->total_bloom_filter_data_size += filter\ndiff --git a/object.h b/object.h\nindex d2f9de6bb5..0a04661a34 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);\n * commit-reach.c: 16-----19\n * sha1-name.c: 20\n * list-objects-filter.c: 21\n+ * bloom.c: 2122\n * builtin/fsck.c: 0--3\n * builtin/gc.c: 0\n * builtin/index-pack.c: 2021\ndiff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh\nindex cc6e5733f6..3f163dc396 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -222,6 +222,10 @@ test_filter_trunc_large () {\n \tgrep \"\\\"key\\\":\\\"filter-trunc-large\\\",\\\"value\\\":\\\"$1\\\"\" $2\n }\n \n+test_filter_upgraded () {\n+\tgrep \"\\\"key\\\":\\\"filter-upgraded\\\",\\\"value\\\":\\\"$1\\\"\" $2\n+}\n+\n test_expect_success 'correctly report changes over limit' '\n \tgit init limits &&\n \t(\n@@ -667,7 +671,14 @@ test_expect_success 'when writing another commit graph, preserve existing versio\n test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '\n \tgit init doublewrite &&\n \ttest_commit -C doublewrite c \"$CENT\" &&\n+\n \tgit -C doublewrite config --add commitGraph.changedPathsVersion 1 &&\n+\t>trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 1 trace2.txt &&\n+\ttest_filter_upgraded 0 trace2.txt &&\n+\n \tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n \tfor v in -2 3\n \tdo\n@@ -678,8 +689,14 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano\n \t\tEOF\n \t\ttest_cmp expect err || return 1\n \tdone &&\n+\n \tgit -C doublewrite config --add commitGraph.changedPathsVersion 2 &&\n-\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\t>trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C doublewrite commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 1 trace2.txt &&\n+\ttest_filter_upgraded 0 trace2.txt &&\n+\n \t(\n \t\tcd doublewrite &&\n \t\techo \"c01f\" >expect &&\n@@ -688,6 +705,26 @@ test_expect_success 'when writing commit graph, do not reuse changed-path of ano\n \t)\n '\n \n+test_expect_success 'when writing commit graph, reuse changed-path of another version where possible' '\n+\tgit init upgrade &&\n+\n+\ttest_commit -C upgrade base no-high-bits &&\n+\n+\tgit -C upgrade config --add commitGraph.changedPathsVersion 1 &&\n+\t>trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C upgrade commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 1 trace2.txt &&\n+\ttest_filter_upgraded 0 trace2.txt &&\n+\n+\tgit -C upgrade config --add commitGraph.changedPathsVersion 2 &&\n+\t>trace2.txt &&\n+\tGIT_TRACE2_EVENT=\"$(pwd)/trace2.txt\" \\\n+\t\tgit -C upgrade commit-graph write --reachable --changed-paths &&\n+\ttest_filter_computed 0 trace2.txt &&\n+\ttest_filter_upgraded 1 trace2.txt\n+'\n+\n corrupt_graph () {\n \ttest_when_finished \"rm -rf $graph\" &&\n \tgit commit-graph write --reachable --changed-paths &&\n-- \n2.45.2.664.g446e6a2b1f\n\n"},{"id":"497653","messageId":"db9991f339377d64b3328cfc1b5e41548b2f8407.1719333276.git.me@ttaylorr.com","threadId":"60826","inReplyTo":"cover.1719333276.git.me@ttaylorr.com","subject":"[PATCH v7 16/16] bloom: introduce `deinit_bloom_filters()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2024-06-25T17:40:15Z","receivedAt":"2024-06-25T17:40:18Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"After we are done using Bloom filters, we do not currently clean up any\nmemory allocated by the commit slab used to store those filters in the\nfirst place.\n\nBesides the bloom_filter structures themselves, there is mostly nothing\nto free() in the first place, since in the read-only path all Bloom\nfilter's `data` members point to a memory mapped region in the\ncommit-graph file itself.\n\nBut when generating Bloom filters from scratch (or initializing\ntruncated filters) we allocate additional memory to store the filter's\ndata.\n\nKeep track of when we need to free() this additional chunk of memory by\nusing an extra pointer `to_free`. Most of the time this will be NULL\n(indicating that we are representing an existing Bloom filter stored in\na memory mapped region). When it is non-NULL, free it before discarding\nthe Bloom filters slab.\n\nSuggested-by: Jonathan Tan \nSigned-off-by: Taylor Blau \nSigned-off-by: Junio C Hamano \nSigned-off-by: Taylor Blau \n---\n bloom.c | 16 +++++++++++++++-\n bloom.h | 3 +++\n commit-graph.c | 4 ++++\n 3 files changed, 22 insertions(+), 1 deletion(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 740c1767ea..d080a1b616 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -92,6 +92,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,\n \t\t\t\t\tsizeof(unsigned char) * start_index +\n \t\t\t\t\tBLOOMDATA_CHUNK_HEADER_SIZE);\n \tfilter->version = g->bloom_filter_settings->hash_version;\n+\tfilter->to_free = NULL;\n \n \treturn 1;\n }\n@@ -264,6 +265,18 @@ void init_bloom_filters(void)\n \tinit_bloom_filter_slab(&bloom_filters);\n }\n \n+static void free_one_bloom_filter(struct bloom_filter *filter)\n+{\n+\tif (!filter)\n+\t\treturn;\n+\tfree(filter->to_free);\n+}\n+\n+void deinit_bloom_filters(void)\n+{\n+\tdeep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter);\n+}\n+\n static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,\n \t\t const struct hashmap_entry *eptr,\n \t\t const struct hashmap_entry *entry_or_key,\n@@ -280,7 +293,7 @@ static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,\n static void init_truncated_large_filter(struct bloom_filter *filter,\n \t\t\t\t\tint version)\n {\n-\tfilter->data = xmalloc(1);\n+\tfilter->data = filter->to_free = xmalloc(1);\n \tfilter->data[0] = 0xFF;\n \tfilter->len = 1;\n \tfilter->version = version;\n@@ -482,6 +495,7 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,\n \t\t\tfilter->len = 1;\n \t\t}\n \t\tCALLOC_ARRAY(filter->data, filter->len);\n+\t\tfilter->to_free = filter->data;\n \n \t\thashmap_for_each_entry(&pathmap, &iter, e, entry) {\n \t\t\tstruct bloom_key key;\ndiff --git a/bloom.h b/bloom.h\nindex e3a9b68905..d20e64bfbb 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -56,6 +56,8 @@ struct bloom_filter {\n \tunsigned char *data;\n \tsize_t len;\n \tint version;\n+\n+\tvoid *to_free;\n };\n \n /*\n@@ -96,6 +98,7 @@ void add_key_to_filter(const struct bloom_key *key,\n \t\t const struct bloom_filter_settings *settings);\n \n void init_bloom_filters(void);\n+void deinit_bloom_filters(void);\n \n enum bloom_filter_computed {\n \tBLOOM_NOT_COMPUTED = (1 << 0),\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 2f0a08f302..c02bef7e72 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -831,6 +831,7 @@ void close_commit_graph(struct raw_object_store *o)\n \t\treturn;\n \n \tclear_commit_graph_data_slab(&commit_graph_data_slab);\n+\tdeinit_bloom_filters();\n \tfree_commit_graph(o->commit_graph);\n \to->commit_graph = NULL;\n }\n@@ -2647,6 +2648,9 @@ int write_commit_graph(struct object_directory *odb,\n \n \tres = write_commit_graph_file(ctx);\n \n+\tif (ctx->changed_paths)\n+\t\tdeinit_bloom_filters();\n+\n \tif (ctx->split)\n \t\tmark_commit_graphs(ctx);\n \n-- \n2.45.2.664.g446e6a2b1f\n"}]}