{"thread":{"id":"60073","subject":"[RFC PATCH 0/6] bloom: reuse existing Bloom filters when possible during upgrade","startedAt":"2023-08-07T16:38:32Z","lastAt":"2023-08-29T22:05:29Z","messageCount":24,"participants":["Taylor Blau","Jonathan Tan"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"480221","messageId":"cover.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":null,"subject":"[RFC PATCH 0/6] bloom: reuse existing Bloom filters when possible during upgrade","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:42Z","receivedAt":"2023-08-07T16:38:32Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"This series is based off of 'jt/path-filter-fix'.\n\nThese few patches implement an idea that we discussed in [1], where we\nattempt to reuse existing Bloom filters during an upgrade from v1 to v2\nBloom filters while rewriting the commit-graph.\n\nThe core idea is that Bloom filters are reusable when there aren't any\nnon-ASCII paths in a commit's tree-diff against its first parent (or the\nempty tree, if none exists). If we assume that a commit's tree-diff\nmeets those conditions, we can't conclude anything about whether either\ntree contains non-ASCII characters, since they could be unmodified on\neither side and thus excluded from the tree-diff.\n\nBut assuming the RHS (that there aren't any non-ASCII characters present\nin the tree's path set) *does* give us that there aren't any such paths\npresent in the first-parent tree diff, either.\n\nThis series checks whether or not commits meet that criteria, and reuses\nthe existing Bloom filter (if one exists) when possible. In practice, we\nend up visiting relatively few trees, since we mark trees we've already\nvisited.\n\nOn both linux.git and git.git, this series gives a significant speed-up\nwhen upgrading Bloom filters from v1 to v2. On linux.git:\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 (where we do have some non-ASCII paths), the change goes from\n4.163 seconds to 3.348 seconds, for a 1.24x speed-up.\n\nI'm sending this as an RFC, since we are in the middle of the -rc phase,\nand 'jt/path-filter-fix' isn't expected[2] to merge into 'master' until\nwe're on the other side of 2.42.\n\nThe structure of this series is as follows:\n\n  - The first three patches prepare to load the `BDAT` chunk, even when\n    the graph's Bloom filter settings are incompatible with the value in\n    `commitGraph.changedPathsVersion`.\n  - The fourth patch begins loading `BDAT` chunks unconditionally.\n  - The fifth patch is a clean-up.\n  - The sixth and final patch implements the approach discussed above.\n\nThanks in advance for your thoughts and review :-).\n\n[1]: https://lore.kernel.org/git/ZMKvsObx+uaKA8zF@nand.local/\n[2]: https://lore.kernel.org/git/xmqqy1it6ykm.fsf@gitster.g/\n\nTaylor Blau (6):\n  bloom: annotate filters with hash version\n  bloom: prepare to discard incompatible Bloom filters\n  t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`\n  commit-graph.c: unconditionally load Bloom filters\n  object.h: fix mis-aligned flag bits table\n  commit-graph: reuse existing Bloom filters where possible\n\n bloom.c              | 117 +++++++++++++++++++++++++++++++++++++++++--\n bloom.h              |  22 +++++++-\n commit-graph.c       |  24 +++++----\n object.h             |   3 +-\n t/t4216-log-bloom.sh |  49 ++++++++++++++++--\n 5 files changed, 195 insertions(+), 20 deletions(-)\n\n-- \n2.41.0.407.g6d1c33951b\n"},{"id":"480222","messageId":"79552bc385a6246f38b6baa1276db13c7300332c.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"[RFC PATCH 3/6] t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:50Z","receivedAt":"2023-08-07T16:38:34Z","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 `commitGraph.changedPathVersion` is\nincompatible with the hash version with which the commit-graph's Bloom\nfilters 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 <me@ttaylorr.com>\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 775e59d864..a77caca789 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -81,7 +81,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.41.0.407.g6d1c33951b\n\n"},{"id":"480223","messageId":"6676afe56db74828ba2532f3460e9b73a3ff20fd.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"[RFC PATCH 4/6] commit-graph.c: unconditionally load Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:53Z","receivedAt":"2023-08-07T16:38:35Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3,\n2023-08-01), we began ignoring the Bloom data (\"BDAT\") chunk for\ncommit-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 <me@ttaylorr.com>\n---\n commit-graph.c | 19 ++++++++++---------\n 1 file changed, 10 insertions(+), 9 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 38edb12669..60e5f9ada7 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -317,12 +317,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n \tuint32_t hash_version;\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-\t} else if (hash_version != *c->commit_graph_changed_paths_version) {\n-\t\treturn 0;\n-\t}\n-\n \tg->chunk_bloom_data = chunk_start;\n \tg->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));\n \tg->bloom_filter_settings->hash_version = hash_version;\n@@ -2390,8 +2384,7 @@ int write_commit_graph(struct object_directory *odb,\n \t\t\tr->settings.commit_graph_changed_paths_version);\n \t\treturn 0;\n \t}\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@@ -2423,10 +2416,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->bloom_filter_settings) {\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.41.0.407.g6d1c33951b\n\n"},{"id":"480224","messageId":"a4cb5fe69247ba737a8373948c1f4ff8a150d283.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"[RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:47Z","receivedAt":"2023-08-07T16:38:38Z","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 <me@ttaylorr.com>\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 9b6a30f6f6..739fa093ba 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -250,6 +250,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@@ -275,7 +292,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 330a140520..2b1c124bb5 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -110,8 +110,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\n+ *   - it has a commit-graph, but reading the commit-graph is disabled\n+ *   - the given commit does not have a Bloom filter computed\n+ *   - there is a Bloom filter for commit \"c\", but it cannot be read because\n+ *     disabled\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.41.0.407.g6d1c33951b\n\n"},{"id":"480225","messageId":"09d6dd93594870c8010c4927c5eb9489ae23e7a2.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"[RFC PATCH 5/6] object.h: fix mis-aligned flag bits table","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:55Z","receivedAt":"2023-08-07T16:38:40Z","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 <me@ttaylorr.com>\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.41.0.407.g6d1c33951b\n\n"},{"id":"480226","messageId":"e23a956401c5619bd46e8ec9b0e1df958cbcbfec.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"[RFC PATCH 1/6] bloom: annotate filters with hash version","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:45Z","receivedAt":"2023-08-07T16:38:52Z","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 \"filter\" field to each\nBloom filter.\n\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\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 ebef5cfd2f..9b6a30f6f6 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -55,6 +55,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@@ -240,11 +241,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@@ -329,13 +332,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@@ -355,7 +360,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 138d57a86b..330a140520 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -55,6 +55,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.41.0.407.g6d1c33951b\n\n"},{"id":"480227","messageId":"93f830ca61d17bb20f63c6a4254fe95816ae1cbe.1691426160.git.me@ttaylorr.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"[RFC PATCH 6/6] commit-graph: reuse existing Bloom filters where possible","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-07T16:37:58Z","receivedAt":"2023-08-07T16:38:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"In 9e4df4da07 (commit-graph: new filter ver. that fixes murmur3,\n2023-08-01), a bug was described where it's possible for Git to produce\nnon-murmur3 hashes when the platform's \"char\" type is signed, and there\nare paths with characters whose highest bit is set (i.e. all characters\n>= 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 <me@ttaylorr.com>\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, 127 insertions(+), 5 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 739fa093ba..24dd874e46 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -7,6 +7,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@@ -250,6 +253,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@@ -292,9 +362,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 2b1c124bb5..4462fc3908 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 60e5f9ada7..62e10c8f40 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1048,6 +1048,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@@ -1654,6 +1655,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@@ -1695,6 +1698,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 a77caca789..48f8109a66 100755\n--- a/t/t4216-log-bloom.sh\n+++ b/t/t4216-log-bloom.sh\n@@ -217,6 +217,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@@ -543,10 +547,19 @@ 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 -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 \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@@ -555,4 +568,22 @@ 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 test_done\n-- \n2.41.0.407.g6d1c33951b\n"},{"id":"480594","messageId":"20230811214651.3326180-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"e23a956401c5619bd46e8ec9b0e1df958cbcbfec.1691426160.git.me@ttaylorr.com","subject":"Re: [RFC PATCH 1/6] bloom: annotate filters with hash version","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-11T21:46:51Z","receivedAt":"2023-08-11T21:47:01Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> In subsequent commits, we will want to load existing Bloom filters out\n> of a commit-graph, even when the hash version they were computed with\n> does not match the value of `commitGraph.changedPathVersion`.\n> \n> In order to differentiate between the two, add a \"filter\" field to each\n> Bloom filter.\n\nYou mean \"version\", I think.\n\n> @@ -55,6 +55,7 @@ struct bloom_filter_settings {\n>  struct bloom_filter {\n>  \tunsigned char *data;\n>  \tsize_t len;\n> +\tint version;\n>  };\n\nWe might want to shrink the sizes of len (we have a changed path limit\nso we know exactly how big Bloom filters can get) and version so that\nthis struct doesn't take up more space. But if other reviewers think\nthat this is OK, I'm fine with that.\n\nAnother thing that we might want to track is whether the Bloom filter is\na reference to an existing buffer (and thus does not need to be freed)\nor a reference to a malloc-ed buffer that we must free. But both before\nand after this patch set, a malloc-ed buffer is never overridden by a\nreference-to-existing-buffer, so we should still be fine for now. (This\npatch set does add a scenario in which a reference-to-existing buffer is\noverridden by a malloc-ed buffer, but that's the only new scenario.)\n"},{"id":"480595","messageId":"20230811214806.3326560-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"a4cb5fe69247ba737a8373948c1f4ff8a150d283.1691426160.git.me@ttaylorr.com","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-11T21:48:06Z","receivedAt":"2023-08-11T21:48:13Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> diff --git a/bloom.h b/bloom.h\n> index 330a140520..2b1c124bb5 100644\n> --- a/bloom.h\n> +++ b/bloom.h\n> @@ -110,8 +110,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\n> + *   - it has a commit-graph, but reading the commit-graph is disabled\n> + *   - the given commit does not have a Bloom filter computed\n> + *   - there is a Bloom filter for commit \"c\", but it cannot be read because\n> + *     disabled\n\ns/disabled/version incompatibility/, I think.\n\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"},{"id":"480598","messageId":"20230811220030.3329161-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"6676afe56db74828ba2532f3460e9b73a3ff20fd.1691426160.git.me@ttaylorr.com","subject":"Re: [RFC PATCH 4/6] commit-graph.c: unconditionally load Bloom filters","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-11T22:00:30Z","receivedAt":"2023-08-11T22:00:45Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 38edb12669..60e5f9ada7 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -317,12 +317,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n>  \tuint32_t hash_version;\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> -\t} else if (hash_version != *c->commit_graph_changed_paths_version) {\n> -\t\treturn 0;\n> -\t}\n\nLots of things to notice in this patch, but the summary is that this\npatch looks correct.\n\nHere, we remove (1) the autodetection of changed paths version and (2)\nthe storage of the result of that autodetection. (1) is restored in a\nsubsequent code hunk, but (2) is never restored.\n\nPrior to this patch set, we needed (2) because we only wanted to load\nBloom filters that match a given version, so if we autodetected a\nversion, that version must be in effect for all future loads (which is\nwhy we needed to store that result immediately). But with this patch\nset, we support the loading of Bloom filters of varying versions, so\nstoring it immediately is no longer needed.\n\n(Also, I don't think we need the commit_graph_changed_paths_version\nvariable anymore.)\n\n> @@ -2390,8 +2384,7 @@ int write_commit_graph(struct object_directory *odb,\n>  \t\t\tr->settings.commit_graph_changed_paths_version);\n>  \t\treturn 0;\n>  \t}\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\nAs stated in the commit message, normalization of the hash version is\nperformed later.\n\n> @@ -2423,10 +2416,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->bloom_filter_settings) {\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\nHere is where the autodetection is restored.\n\nPrior to this patch set, this part of the code does not perform\nautodetection - every hash_version in memory matches the version in\ncommit_graph_changed_paths_version, so we're just copying over the value\nin that variable. But the nature of this part of the code has changed\ndue to this patch set: all the g->bloom_filter_settings in memory\nmay not have the same hash version, and may not match what the user\nspecified in config. To compensate, we are more selective in what we\npropagate from g->bloom_filter_settings.\n\n> +\tbloom_settings.hash_version = bloom_settings.hash_version == 2 ? 2 : 1;\n\nAnd here we restore the normalization.\n\nThanks - up to here looks good.\n"},{"id":"480599","messageId":"20230811220637.3330277-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"93f830ca61d17bb20f63c6a4254fe95816ae1cbe.1691426160.git.me@ttaylorr.com","subject":"Re: [RFC PATCH 6/6] commit-graph: reuse existing Bloom filters where possible","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-11T22:06:37Z","receivedAt":"2023-08-11T22:06:53Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> @@ -292,9 +362,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\nThere's a part in this function that's untouched by the diff that\ncomputes and stores a new Bloom filter if it was not possible to upgrade\nthe filter (look at the part where filter->data is calloc-ed). That\npart unconditionally overrides the existing filter->data, which may at\nthat point contain genuine data (a Bloom filter that does not match the\nversion we want). Right now this is fine because all overrides that we\ndo involve overriding references to existing buffers, so we do not need\nto free anything.\n"},{"id":"480602","messageId":"20230811221337.3331688-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"cover.1691426160.git.me@ttaylorr.com","subject":"Re: [RFC PATCH 0/6] bloom: reuse existing Bloom filters when possible during upgrade","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-11T22:13:37Z","receivedAt":"2023-08-11T22:13:53Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> On both linux.git and git.git, this series gives a significant speed-up\n> when upgrading Bloom filters from v1 to v2. On linux.git:\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> \n> On git.git (where we do have some non-ASCII paths), the change goes from\n> 4.163 seconds to 3.348 seconds, for a 1.24x speed-up.\n\nMy main concern is that this modifies the code somewhat pervasively\n(tracking the version of Bloom filters and removing assumptions about\nwhat Bloom filter versions are in memory) in return for what I think\nis a small speedup, when considering that we will perform this\noperation only once for a given repo. I'll defer to server operators\non this (or other people handling large numbers of repos), though.\n\nPutting that concern aside, I've reviewed the code and assuming that\nwe're OK with modifying the code in this way, this patch set looks good\nto me, and hopefully my review will be of some help.\n"},{"id":"480761","messageId":"ZN57Gsz+wk9n6/Da@nand.local","threadId":"60073","inReplyTo":"20230811214651.3326180-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 1/6] bloom: annotate filters with hash version","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-17T19:55:06Z","receivedAt":"2023-08-17T19:56:00Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Aug 11, 2023 at 02:46:51PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > In subsequent commits, we will want to load existing Bloom filters out\n> > of a commit-graph, even when the hash version they were computed with\n> > does not match the value of `commitGraph.changedPathVersion`.\n> >\n> > In order to differentiate between the two, add a \"filter\" field to each\n> > Bloom filter.\n>\n> You mean \"version\", I think.\n\nOops, yes -- I'm not sure how my editor tab-completed \"version\" there,\nbut oh, well :-).\n\n> > @@ -55,6 +55,7 @@ struct bloom_filter_settings {\n> >  struct bloom_filter {\n> >  \tunsigned char *data;\n> >  \tsize_t len;\n> > +\tint version;\n> >  };\n>\n> We might want to shrink the sizes of len (we have a changed path limit\n> so we know exactly how big Bloom filters can get) and version so that\n> this struct doesn't take up more space. But if other reviewers think\n> that this is OK, I'm fine with that.\n\nI think that making len a size_t here is an appropriate choice. Even\nthough the maximum length of a Bloom filter is well below the 2^64-1\nthreshold, we are often looking at a memory-mapped region here, so\nkeeping track of it with a size_t / off_t seems reasonable to me.\n\n> Another thing that we might want to track is whether the Bloom filter is\n> a reference to an existing buffer (and thus does not need to be freed)\n> or a reference to a malloc-ed buffer that we must free. But both before\n> and after this patch set, a malloc-ed buffer is never overridden by a\n> reference-to-existing-buffer, so we should still be fine for now. (This\n> patch set does add a scenario in which a reference-to-existing buffer is\n> overridden by a malloc-ed buffer, but that's the only new scenario.)\n\nYeah, I think there is some opportunity for clean-up here. I'll take a\nlook...\n\nThanks,\nTaylor\n"},{"id":"480869","messageId":"ZOPHXcTMlB77CsCh@nand.local","threadId":"60073","inReplyTo":"ZN57Gsz+wk9n6/Da@nand.local","subject":"Re: [RFC PATCH 1/6] bloom: annotate filters with hash version","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-21T20:21:49Z","receivedAt":"2023-08-21T20:21:55Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Aug 17, 2023 at 03:55:06PM -0400, Taylor Blau wrote:\n> > Another thing that we might want to track is whether the Bloom filter is\n> > a reference to an existing buffer (and thus does not need to be freed)\n> > or a reference to a malloc-ed buffer that we must free. But both before\n> > and after this patch set, a malloc-ed buffer is never overridden by a\n> > reference-to-existing-buffer, so we should still be fine for now. (This\n> > patch set does add a scenario in which a reference-to-existing buffer is\n> > overridden by a malloc-ed buffer, but that's the only new scenario.)\n>\n> Yeah, I think there is some opportunity for clean-up here. I'll take a\n> look...\n\nThis ended up being pretty reasonable. I'm not sure whether I should\ninclude it here or not, since any leaks in the Bloom subsystem are\ndefinitely not new as of this series.\n\nBut the patch is relatively straightforward anyway, so I think throwing\nit on the end would be OK:\n\n--- 8< ---\ndiff --git a/bloom.c b/bloom.c\nindex 24dd874e46..ff131893cd 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -59,6 +59,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@@ -231,6 +232,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@@ -247,7 +260,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@@ -449,6 +462,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 4462fc3908..c1d74d63e6 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 183ed90b6d..f22f2d350d 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -2532,6 +2532,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--- >8 ---\n\nThanks,\nTaylor\n"},{"id":"480870","messageId":"ZOPH1714y4iPyeB5@nand.local","threadId":"60073","inReplyTo":"20230811214806.3326560-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-21T20:23:51Z","receivedAt":"2023-08-21T20:23:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Aug 11, 2023 at 02:48:06PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > diff --git a/bloom.h b/bloom.h\n> > index 330a140520..2b1c124bb5 100644\n> > --- a/bloom.h\n> > +++ b/bloom.h\n> > @@ -110,8 +110,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\n> > + *   - it has a commit-graph, but reading the commit-graph is disabled\n> > + *   - the given commit does not have a Bloom filter computed\n> > + *   - there is a Bloom filter for commit \"c\", but it cannot be read because\n> > + *     disabled\n>\n> s/disabled/version incompatibility/, I think.\n\nWell spotted, thanks.\n\nThanks,\nTaylor\n"},{"id":"480874","messageId":"ZOPLphXoMjq876Wk@nand.local","threadId":"60073","inReplyTo":"20230811220030.3329161-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 4/6] commit-graph.c: unconditionally load Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-21T20:40:06Z","receivedAt":"2023-08-21T20:41:05Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Aug 11, 2023 at 03:00:30PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > diff --git a/commit-graph.c b/commit-graph.c\n> > index 38edb12669..60e5f9ada7 100644\n> > --- a/commit-graph.c\n> > +++ b/commit-graph.c\n> > @@ -317,12 +317,6 @@ static int graph_read_bloom_data(const unsigned char *chunk_start,\n> >  \tuint32_t hash_version;\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> > -\t} else if (hash_version != *c->commit_graph_changed_paths_version) {\n> > -\t\treturn 0;\n> > -\t}\n>\n> Lots of things to notice in this patch, but the summary is that this\n> patch looks correct.\n\nThanks for the detailed analysis here. This is definitely the patch that\nI was most nervous about while writing, but I appreciate the second set\nof eyes.\n\n> (Also, I don't think we need the commit_graph_changed_paths_version\n> variable anymore.)\n\nGreat catch, thanks. I cleaned that up in a separate commit after this\none, since I think that this patch is already intricate enough.\n\nThanks,\nTaylor\n"},{"id":"480877","messageId":"ZOPNPU/cekgJU7S7@nand.local","threadId":"60073","inReplyTo":"20230811221337.3331688-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 0/6] bloom: reuse existing Bloom filters when possible during upgrade","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-21T20:46:53Z","receivedAt":"2023-08-21T20:47:07Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Aug 11, 2023 at 03:13:37PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > On both linux.git and git.git, this series gives a significant speed-up\n> > when upgrading Bloom filters from v1 to v2. On linux.git:\n> >\n> >     Benchmark 1: GIT_TEST_UPGRADE_BLOOM_FILTERS=0 git.compile commit\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> >\n> > On git.git (where we do have some non-ASCII paths), the change goes from\n> > 4.163 seconds to 3.348 seconds, for a 1.24x speed-up.\n>\n> My main concern is that this modifies the code somewhat pervasively\n> (tracking the version of Bloom filters and removing assumptions about\n> what Bloom filter versions are in memory) in return for what I think\n> is a small speedup, when considering that we will perform this\n> operation only once for a given repo. I'll defer to server operators\n> on this (or other people handling large numbers of repos), though.\n\nYeah, I think that this is certainly on the riskier side of things. But\nI have confidence in our test coverage here, and feel better with your\nthorough review.\n\nFWIW, I think that the speed-up is worthwhile (though I'm obviously\nbiased here). When we were rolling out changed-path Bloom filters to\nrepositories on GitHub.com, it was apparent that computing them from\nscratch in a single shot was infeasible. This led to 809e0327f5\n(builtin/commit-graph.c: introduce '--max-new-filters=<n>', 2020-09-18).\n\nThat would of course still save us here if we didn't have an upgrade\npath, since each recomputed filter would count against the maximum\nnumber we can generate in a single run.\n\nWe could introduce a configuration knob, but I'd rather avoid it if\npossible. That can also be done on top in a later patch, which should be\neasy enough to do if we hear of a compelling use-case for wanting to\ndisable the upgrade path here.\n\n> Putting that concern aside, I've reviewed the code and assuming that\n> we're OK with modifying the code in this way, this patch set looks good\n> to me, and hopefully my review will be of some help.\n\nThanks very much -- it was more than helpful :-). I'll collect up this\nand your previous patches (as we have discussed off-list) and tie\neverything together in a single series for the maintainer.\n\nThanks,\nTaylor\n"},{"id":"481021","messageId":"20230824222051.2320003-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"a4cb5fe69247ba737a8373948c1f4ff8a150d283.1691426160.git.me@ttaylorr.com","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-24T22:20:51Z","receivedAt":"2023-08-24T22:22:10Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> diff --git a/bloom.c b/bloom.c\n> index 9b6a30f6f6..739fa093ba 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -250,6 +250,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\nI missed this the last time, but this should match what fill_bloom_key()\ndoes. Use get_bloom_filter_settings(), then compare filter->version to\nversion 2 if hash_version is 2, and to version 1 otherwise.\n\nEverything else looks good.\n \n"},{"id":"481023","messageId":"ZOfeE1K8aRIECVm4@nand.local","threadId":"60073","inReplyTo":"20230824222051.2320003-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-24T22:47:47Z","receivedAt":"2023-08-24T22:48:33Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Aug 24, 2023 at 03:20:51PM -0700, Jonathan Tan wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n> > diff --git a/bloom.c b/bloom.c\n> > index 9b6a30f6f6..739fa093ba 100644\n> > --- a/bloom.c\n> > +++ b/bloom.c\n> > @@ -250,6 +250,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> I missed this the last time, but this should match what fill_bloom_key()\n> does. Use get_bloom_filter_settings(),\n\nI'm not sure I'm following. Are you saying that we should use\nget_bloom_filter_settings() instead of reading the value from\nr->settings directly?\n\n> then compare filter->version to version 2 if hash_version is 2, and to\n> version 1 otherwise.\n\nHmm. I think we're already doing the right thing here, no? IIUC, you're\nsaying to do something like:\n\n    struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n    struct bloom_filter *f = get_or_compute_bloom_filter(r, c, ...);\n    int hash_version;\n\n    if (!f)\n      return NULL;\n\n    prepare_repo_settings(r);\n    hash_version = r->settings.commit_graph_changed_paths_version;\n\n    if (!(hash_version == -1 || hash_version == s->hash_version))\n      return NULL; /* incompatible */\n    return f;\n\n?\n\nIf so, I think that we're already OK here, since s->hash_version is\nalways going to take the same value as f->version, since f->version is\nassigned in bloom.c::load_bloom_filter_from_graph(), which does:\n\n    filter->version = g->bloom_filter_settings->hash_version;\n\nOr are we talking about two different things entirely? ;-)\n\nThanks,\nTaylor\n"},{"id":"481025","messageId":"20230824230527.2332958-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"ZOfeE1K8aRIECVm4@nand.local","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-24T23:05:27Z","receivedAt":"2023-08-24T23:06:32Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> I'm not sure I'm following. Are you saying that we should use\n> get_bloom_filter_settings() instead of reading the value from\n> r->settings directly?\n> \n> > then compare filter->version to version 2 if hash_version is 2, and to\n> > version 1 otherwise.\n> \n> Hmm. I think we're already doing the right thing here, no? IIUC, you're\n> saying to do something like:\n> \n>     struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n>     struct bloom_filter *f = get_or_compute_bloom_filter(r, c, ...);\n>     int hash_version;\n> \n>     if (!f)\n>       return NULL;\n> \n>     prepare_repo_settings(r);\n>     hash_version = r->settings.commit_graph_changed_paths_version;\n> \n>     if (!(hash_version == -1 || hash_version == s->hash_version))\n>       return NULL; /* incompatible */\n>     return f;\n> \n> ?\n> \n> If so, I think that we're already OK here, since s->hash_version is\n> always going to take the same value as f->version, since f->version is\n> assigned in bloom.c::load_bloom_filter_from_graph(), which does:\n> \n>     filter->version = g->bloom_filter_settings->hash_version;\n> \n> Or are we talking about two different things entirely? ;-)\n> \n> Thanks,\n> Taylor\n\nAh, sorry for not being clear. What I meant is in how you compute\nhash_version after we have found that filter is not NULL.\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\nUp to here is fine.\n\n> +\thash_version = r->settings.commit_graph_changed_paths_version;\n\nInstead of doing this, do this (well, move the struct declaration to\nthe top):\n\n  struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n  hash_version = s->hash_version == 2 ? 2 : 1;\n  \n> +\tif (!(hash_version == -1 || hash_version == filter->version))\n\nNo need for the comparison to -1 here.\n\n> +\t\treturn NULL; /* unusable filter */\n> +\treturn filter;\n> +}\n\nThis is fine.\n\n\n"},{"id":"481033","messageId":"ZOj6PazHzDeQrY88@nand.local","threadId":"60073","inReplyTo":"20230824230527.2332958-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-25T19:00:13Z","receivedAt":"2023-08-25T19:00:56Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Aug 24, 2023 at 04:05:27PM -0700, Jonathan Tan wrote:\n> Up to here is fine.\n>\n> > +\thash_version = r->settings.commit_graph_changed_paths_version;\n>\n> Instead of doing this, do this (well, move the struct declaration to\n> the top):\n>\n>   struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n>   hash_version = s->hash_version == 2 ? 2 : 1;\n\nDo we need this normalization? We assign s->hash_version in\ncommit-graph.c::graph_read_bloom_data() by reading it from the start of\nthe BDAT chunk, so this should only ever be 1 or 2.\n\n> > +\tif (!(hash_version == -1 || hash_version == filter->version))\n>\n> No need for the comparison to -1 here.\n\nI'm not sure I understand your suggestion. When we fetch the filter from\nget_or_compute_bloom_filter(), we have filter->version set to the\nhash_version from the containing graph's Bloom filter settings.\n\nSo (besides the normalization), I would think that:\n\n    struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n    struct bloom_filter *f = get_bloom_filter(...);\n\n    assert(s->hash_version == f->version);\n\nwould hold.\n\nI think the check that we want to make is instead: is this Bloom\nfilter's version (or equivalently, the hash version indicated by that\ngraph's BDAT chunk) something that we can read? And I think \"what we can\nread\" here is dictated by the commit_graph_changed_paths_version member\nof our repository_settings, no?\n\nThanks,\nTaylor\n"},{"id":"481121","messageId":"20230829164926.367260-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"ZOj6PazHzDeQrY88@nand.local","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-29T16:49:26Z","receivedAt":"2023-08-29T16:50:33Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Taylor Blau <me@ttaylorr.com> writes:\n> On Thu, Aug 24, 2023 at 04:05:27PM -0700, Jonathan Tan wrote:\n> > Up to here is fine.\n> >\n> > > +\thash_version = r->settings.commit_graph_changed_paths_version;\n> >\n> > Instead of doing this, do this (well, move the struct declaration to\n> > the top):\n> >\n> >   struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n> >   hash_version = s->hash_version == 2 ? 2 : 1;\n> \n> Do we need this normalization? We assign s->hash_version in\n> commit-graph.c::graph_read_bloom_data() by reading it from the start of\n> the BDAT chunk, so this should only ever be 1 or 2.\n\nI'm not sure offhand if we do...I wrote it this way to match\nfill_bloom_key(), but fill_bloom_key() was written in that way because\nit was the clearest, not specifically because it needed to normalize.\n\n> > > +\tif (!(hash_version == -1 || hash_version == filter->version))\n> >\n> > No need for the comparison to -1 here.\n> \n> I'm not sure I understand your suggestion. When we fetch the filter from\n> get_or_compute_bloom_filter(), we have filter->version set to the\n> hash_version from the containing graph's Bloom filter settings.\n> \n> So (besides the normalization), I would think that:\n> \n>     struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n>     struct bloom_filter *f = get_bloom_filter(...);\n> \n>     assert(s->hash_version == f->version);\n> \n> would hold.\n\nMy mention to avoid the comparison to -1 was just for completeness\n- since we're normalizing the value of hash_version to 1 or 2, we no\nlonger need to compare it to -1.\n\nAs for whether s->hash_version is always equal to f->version, I think\nthat it may not be true if for some reason, there are multiple commit\ngraph files on disk, not all with the same Bloom filter version.\n\n> I think the check that we want to make is instead: is this Bloom\n> filter's version (or equivalently, the hash version indicated by that\n> graph's BDAT chunk) something that we can read? \n\nI think it's not \"something that we can read\" (eventually, we can read\nall versions, we just treat them differently) but \"the version that\nfill_bloom_key\" will use. We don't want this function to produce a Bloom\nfilter of version X and then have the calling code subsequently use it\nwith a Bloom key of version Y.\n\n> And I think \"what we can\n> read\" here is dictated by the commit_graph_changed_paths_version member\n> of our repository_settings, no?\n\nI don't think commit_graph_changed_paths_version always dictates\nsomething - it could be -1 (which you have probably seen, since you\ncheck it against -1 in the current version of the patch). One of the\npoints of my suggestion is to avoid this field completely.\n"},{"id":"481132","messageId":"ZO5DheoYy/syeJ+9@nand.local","threadId":"60073","inReplyTo":"20230829164926.367260-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2023-08-29T19:14:13Z","receivedAt":"2023-08-29T19:15:01Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Aug 29, 2023 at 09:49:26AM -0700, Jonathan Tan wrote:\n> > > > +\tif (!(hash_version == -1 || hash_version == filter->version))\n> > >\n> > > No need for the comparison to -1 here.\n> >\n> > I'm not sure I understand your suggestion. When we fetch the filter from\n> > get_or_compute_bloom_filter(), we have filter->version set to the\n> > hash_version from the containing graph's Bloom filter settings.\n> >\n> > So (besides the normalization), I would think that:\n> >\n> >     struct bloom_filter_settings *s = get_bloom_filter_settings(r);\n> >     struct bloom_filter *f = get_bloom_filter(...);\n> >\n> >     assert(s->hash_version == f->version);\n> >\n> > would hold.\n>\n> My mention to avoid the comparison to -1 was just for completeness\n> - since we're normalizing the value of hash_version to 1 or 2, we no\n> longer need to compare it to -1.\n>\n> As for whether s->hash_version is always equal to f->version, I think\n> that it may not be true if for some reason, there are multiple commit\n> graph files on disk, not all with the same Bloom filter version.\n\nApologies for not quite grokking this, but I am still somewhat confused.\n\nSuppose we applied something like your suggestion on top of this patch,\nlike so:\n\n--- 8< ---\ndiff --git a/bloom.c b/bloom.c\nindex 739fa093ba..ee81976342 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -253,16 +253,16 @@ static void init_truncated_large_filter(struct bloom_filter *filter,\n struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n {\n \tstruct bloom_filter *filter;\n-\tint hash_version;\n+\tstruct bloom_filter_settings *settings;\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+\tsettings = get_bloom_filter_settings(r);\n\n-\tif (!(hash_version == -1 || hash_version == filter->version))\n+\tif (filter->version != (settings->hash_version == 2 ? 2 : 1))\n \t\treturn NULL; /* unusable filter */\n \treturn filter;\n }\n--- >8 ---\n\nWe have a handful of failing tests, notably including t4216.1, which\ntries to read settings->hash_version, but fails since settings is NULL.\nI believe this happens when we have a computed Bloom filter prepared for\nsome commit, but have not yet written a commit graph containing that (or\nany) Bloom filter.\n\nBut I think we're talking about different things here. The point of\nget_bloom_filter() as a wrapper around get_or_compute_bloom_filter() is\nto only return Bloom filters that are readable under the configuration\ncommitGraph.changedPathsVersion.\n\nWe have a handle on what version was used to compute Bloom filters in\neach layer of the graph by reading its \"version\" field, which is written\nvia load_bloom_filter_from_graph().\n\nSo we want to return a non-NULL filter exactly when we (a) have a Bloom\nfilter computed for the given commit, and (b) its version matches the\nversion specified in commitGraph.chagnedPathsVersion.\n\nAre you saying that we need to do the normalization ahead of time so\nthat we don't emit filters that have different hash versions when\nworking in a commit-graph chain where each layer may use different Bloom\nfilter settings? If so, then I think the change we'd need to make is\nlimited to:\n\n--- 8< ---\ndiff --git a/bloom.c b/bloom.c\nindex 739fa093ba..d5cc23b0a8 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -260,9 +260,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n \t\treturn NULL;\n\n \tprepare_repo_settings(r);\n-\thash_version = r->settings.commit_graph_changed_paths_version;\n+\thash_version = r->settings.commit_graph_changed_paths_version == 2 ? 2 : 1;\n\n-\tif (!(hash_version == -1 || hash_version == filter->version))\n+\tif (hash_version == filter->version)\n \t\treturn NULL; /* unusable filter */\n \treturn filter;\n }\n--- >8 ---\n\nBut that doesn't quite work, either, since it's breaking some assumption\nfrom the caller and causing us not to write out any Bloom filters (I\nhaven't investigated further, but I'm not sure that this is the right\npath in the first place...).\n\nSo I am not sure what you are suggesting, but I am sure that I'm missing\nsomething.\n\nThanks,\nTaylor\n"},{"id":"481137","messageId":"20230829220432.558674-1-jonathantanmy@google.com","threadId":"60073","inReplyTo":"ZO5DheoYy/syeJ+9@nand.local","subject":"Re: [RFC PATCH 2/6] bloom: prepare to discard incompatible Bloom filters","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2023-08-29T22:04:32Z","receivedAt":"2023-08-29T22:05:29Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"Here are answers to your questions, but I'll also reply to the latest\nversion stating that I'm OK with this patch set being merged (with my\nreasons).\n\nTaylor Blau <me@ttaylorr.com> writes:\n> Apologies for not quite grokking this, but I am still somewhat confused.\n> \n> Suppose we applied something like your suggestion on top of this patch,\n> like so:\n> \n> --- 8< ---\n> diff --git a/bloom.c b/bloom.c\n> index 739fa093ba..ee81976342 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -253,16 +253,16 @@ static void init_truncated_large_filter(struct bloom_filter *filter,\n>  struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)\n>  {\n>  \tstruct bloom_filter *filter;\n> -\tint hash_version;\n> +\tstruct bloom_filter_settings *settings;\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> +\tsettings = get_bloom_filter_settings(r);\n> \n> -\tif (!(hash_version == -1 || hash_version == filter->version))\n> +\tif (filter->version != (settings->hash_version == 2 ? 2 : 1))\n>  \t\treturn NULL; /* unusable filter */\n>  \treturn filter;\n>  }\n> --- >8 ---\n> \n> We have a handful of failing tests, notably including t4216.1, which\n> tries to read settings->hash_version, but fails since settings is NULL.\n> I believe this happens when we have a computed Bloom filter prepared for\n> some commit, but have not yet written a commit graph containing that (or\n> any) Bloom filter.\n\nAh, I discovered this independently too. I think it happens when we\nwrite version 2 Bloom filters to a repo that has no Bloom filters\ncurrently. So, r->settings.commit_graph_changed_paths_version is set to\n2, but settings is NULL. I think the solution has to be a combination\nof both (use commit_graph_changed_paths_version, but if it is -1, check\nget_bloom_filter_settings()). But having said that, as I said above, we\ncan go with what you have currently.\n\n> But I think we're talking about different things here. The point of\n> get_bloom_filter() as a wrapper around get_or_compute_bloom_filter() is\n> to only return Bloom filters that are readable under the configuration\n> commitGraph.changedPathsVersion.\n\nBut this is my contention - sometimes commitGraph.changedPathsVersion is\n-1, so we need to find out which version is readable from elsewhere.\n\n> We have a handle on what version was used to compute Bloom filters in\n> each layer of the graph by reading its \"version\" field, which is written\n> via load_bloom_filter_from_graph().\n> \n> So we want to return a non-NULL filter exactly when we (a) have a Bloom\n> filter computed for the given commit, and (b) its version matches the\n> version specified in commitGraph.chagnedPathsVersion.\n\nYes, except add \"or autodetected from the first commit graph file that\nwe read if nothing is specified in commitGraph.changedPathsVersion\" to\nthe end.\n\n> Are you saying that we need to do the normalization ahead of time so\n> that we don't emit filters that have different hash versions when\n> working in a commit-graph chain where each layer may use different Bloom\n> filter settings? \n\nBy \"emit\" do you mean write filters to disk? If yes, I'm worried about\nreading them, not writing them - for example, when running \"git log\"\nwith a path. I am worried precisely about the commit-graph chain in\nwhich different layers have different Bloom settings, yes.\n"}]}