From: Derrick Stolee <derrickstolee@github.com>
To: Jonathan Tan <jonathantanmy@google.com>, git@vger.kernel.org
Cc: Ramsay Jones <ramsay@ramsayjones.plus.com>,
Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH v4 4/4] commit-graph: new filter ver. that fixes murmur3
Date: Tue, 20 Jun 2023 09:39:09 -0400 [thread overview]
Message-ID: <4c5cadf2-bd70-c56e-3935-fb24b604f411@github.com> (raw)
In-Reply-To: <5c65bf8a22d657c58b1109928b4298e95ccb56bf.1686677910.git.jonathantanmy@google.com>
On 6/13/2023 1:39 PM, Jonathan Tan wrote:
> commitGraph.changedPathsVersion::
> Specifies the version of the changed-path Bloom filters that Git will read and
> - write. May be 0 or 1. Any changed-path Bloom filters on disk that do not
> + write. May be 0, 1, or 2. Any changed-path Bloom filters on disk that do not
> match the version set in this config variable will be ignored.
> +
> Defaults to 1.
Is this a good place to document the planned modification of this default in
future versions of Git?
> +static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)
> {
> const uint32_t c1 = 0xcc9e2d51;
> const uint32_t c2 = 0x1b873593;
> @@ -130,8 +187,10 @@ void fill_bloom_key(const char *data,
> int i;
> const uint32_t seed0 = 0x293ae76f;
> const uint32_t seed1 = 0x7e646e2c;
> - const uint32_t hash0 = murmur3_seeded(seed0, data, len);
> - const uint32_t hash1 = murmur3_seeded(seed1, data, len);
> + const uint32_t hash0 = (settings->hash_version == 2
> + ? murmur3_seeded_v2 : murmur3_seeded_v1)(seed0, data, len);
> + const uint32_t hash1 = (settings->hash_version == 2
> + ? murmur3_seeded_v2 : murmur3_seeded_v1)(seed1, data, len);
This is the critical step. I've not seen this ternary trick within
a function name choice, but it makes for a compact check. Nice.
However, I think the 'settings->hash_version' is the wrong place
to look for the condition. We should be getting this value from the
commit-graph we are reading. (More on this later.)
> struct bloom_filter_settings {
> /*
> * The version of the hashing technique being used.
> - * We currently only support version = 1 which is
> + * The newest version is 2, which is
> * the seeded murmur3 hashing technique implemented
> - * in bloom.c.
> + * in bloom.c. Bloom filters of version 1 were created
> + * with prior versions of Git, which had a bug in the
> + * implementation of the hash function.
...
> +struct graph_read_bloom_data_data {
> + struct commit_graph *g;
> + int commit_graph_changed_paths_version;
> +};
> +
> static int graph_read_bloom_data(const unsigned char *chunk_start,
> size_t chunk_size, void *data)
> {
> - struct commit_graph *g = data;
> + struct graph_read_bloom_data_data *d = data;
> + struct commit_graph *g = d->g;
> uint32_t hash_version;
> g->chunk_bloom_data = chunk_start;
> hash_version = get_be32(chunk_start);
>
> - if (hash_version != 1)
> + if (hash_version != d->commit_graph_changed_paths_version)
> return 0;
This makes it appear like we cannot read a commit-graph that has
a Bloom filter version that doesn't match the configured version.
This seems incorrect. If we want to configure to _write_ v2, we
should still be able to _read_ v1 concurrently until those v2
filters are written.
This check should be:
if (hash_version <= 0 || hash_version > 2)
return 0;
and then
g->filter_hash_version = hash_version;
to store this hash version somewhere in the graph. This way, we
can read any commit-graph file and will not suffer performance
problems in the time between setting the config value and writing
the new commit-graph file.
> - if (s->commit_graph_changed_paths_version == 1) {
> + if (s->commit_graph_changed_paths_version == 1
> + || s->commit_graph_changed_paths_version == 2) {
Perhaps this could just be
if (s->commit_graph_changed_paths_version) {
to say "not zero means we still read the filters". Though, since
this config _should_ mean "which version do we _write_?" it might
be good to go back on the "unifying the two config options".
> + struct graph_read_bloom_data_data data = {
> + .g = graph,
> + .commit_graph_changed_paths_version = s->commit_graph_changed_paths_version
> + };
> pair_chunk(cf, GRAPH_CHUNKID_BLOOMINDEXES,
> &graph->chunk_bloom_indexes);
> read_chunk(cf, GRAPH_CHUNKID_BLOOMDATA,
> - graph_read_bloom_data, graph);
> + graph_read_bloom_data, &data);
> }
Much of this block will not be necessary as we don't need to
send the repo settings into the read_chunk() method.
> + if (r->settings.commit_graph_changed_paths_version < 0
> + || r->settings.commit_graph_changed_paths_version > 2) {
> + warning(_("attempting to write a commit-graph, but 'commitgraph.changedPathsVersion' (%d) is not supported"),
> + r->settings.commit_graph_changed_paths_version);
> + return 0;
I see the "< 0" means we aren't considering the case of disabling
writes with the zero value. We should exit early if we see a zero
here, for extra safety.
> + }
> + bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2
> + ? 2 : 1;
Once we've checked that this value is not zero, we can do this:
bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version;
> /* We have changed-paths already. Keep them in the next graph */
> - if (g && g->chunk_bloom_data) {
> + if (g && g->bloom_filter_settings) {
> ctx->changed_paths = 1;
> ctx->bloom_settings = g->bloom_filter_settings;
> }
> --- a/t/t4216-log-bloom.sh
> +++ b/t/t4216-log-bloom.sh
> @@ -450,4 +450,35 @@ test_expect_success 'version 1 changed-path used when version 1 requested' '
> test_bloom_filters_used "-- $CENT")
> '
>
> +test_expect_success 'version 1 changed-path not used when version 2 requested' '
> + (cd highbit1 &&
> + git config --add commitgraph.changedPathsVersion 2 &&
> + test_bloom_filters_not_used "-- $CENT")
> +'
I think this test is the wrong behavior. We should be able to use version 1
when version 2 is requested.
Instead, start with version 1, and _upgrade_ to version 2 and then check
which version exists in the file.
We should only _not_ use the filters if the version is 0 (or
commitGraph.readChangedPaths=false). I think this might be a good enough reason
to
> +
> +test_expect_success 'set up repo with high bit path, version 2 changed-path' '
> + git init highbit2 &&
> + git -C highbit2 config --add commitgraph.changedPathsVersion 2 &&
> + test_commit -C highbit2 c2 "$CENT" &&
> + git -C highbit2 commit-graph write --reachable --changed-paths
> +'
> +
> +test_expect_success 'check value of version 2 changed-path' '
> + (cd highbit2 &&
> + printf "c01f" >expect &&
> + get_first_changed_path_filter >actual &&
> + test_cmp expect actual)
> +'
> +
> +test_expect_success 'version 2 changed-path used when version 2 requested' '
> + (cd highbit2 &&
> + test_bloom_filters_used "-- $CENT")
> +'
> +
> +test_expect_success 'version 2 changed-path not used when version 1 requested' '
> + (cd highbit2 &&
> + git config --add commitgraph.changedPathsVersion 1 &&
> + test_bloom_filters_not_used "-- $CENT")
> +'
Again, this is also the wrong situation.
Thanks,
-Stolee
next prev parent reply other threads:[~2023-06-20 13:39 UTC|newest]
Thread overview: 116+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-22 21:48 [PATCH 0/2] Changed path filter hash fix and version bump Jonathan Tan
2023-05-22 21:48 ` [PATCH 1/2] t4216: test wrong bloom filter version rejection Jonathan Tan
2023-05-22 21:48 ` [PATCH 2/2] commit-graph: fix murmur3, bump filter ver. to 2 Jonathan Tan
2023-05-23 13:00 ` Derrick Stolee
2023-05-23 23:00 ` Jonathan Tan
2023-05-23 23:51 ` Junio C Hamano
2023-05-24 21:26 ` Jonathan Tan
2023-05-26 13:19 ` Derrick Stolee
2023-05-30 17:26 ` Jonathan Tan
2023-05-23 4:42 ` [PATCH 0/2] Changed path filter hash fix and version bump Junio C Hamano
2023-05-31 23:12 ` [PATCH v2 0/3] " Jonathan Tan
2023-05-31 23:12 ` [PATCH v2 1/3] t4216: test changed path filters with high bit paths Jonathan Tan
2023-05-31 23:12 ` [PATCH v2 2/3] repo-settings: introduce commitgraph.changedPathsVersion Jonathan Tan
2023-05-31 23:12 ` [PATCH v2 3/3] commit-graph: new filter ver. that fixes murmur3 Jonathan Tan
2023-06-03 1:01 ` [PATCH v2 0/3] Changed path filter hash fix and version bump Junio C Hamano
2023-06-03 2:24 ` Junio C Hamano
2023-06-07 16:30 ` Jonathan Tan
2023-06-07 21:37 ` Jonathan Tan
2023-06-08 19:21 ` [PATCH v3 0/4] " Jonathan Tan
2023-06-08 19:21 ` [PATCH v3 1/4] gitformat-commit-graph: describe version 2 of BDAT Jonathan Tan
2023-06-08 19:52 ` Ramsay Jones
2023-06-12 21:26 ` Junio C Hamano
2023-06-08 19:21 ` [PATCH v3 2/4] t4216: test changed path filters with high bit paths Jonathan Tan
2023-06-08 19:21 ` [PATCH v3 3/4] repo-settings: introduce commitgraph.changedPathsVersion Jonathan Tan
2023-06-08 19:21 ` [PATCH v3 4/4] commit-graph: new filter ver. that fixes murmur3 Jonathan Tan
2023-06-08 19:50 ` [PATCH v3 0/4] Changed path filter hash fix and version bump Ramsay Jones
2023-06-09 0:08 ` Jonathan Tan
2023-06-12 21:31 ` Junio C Hamano
2023-06-13 17:16 ` Jonathan Tan
2023-06-13 17:29 ` [PATCH] CodingGuidelines: use octal escapes, not hex Jonathan Tan
2023-06-13 18:16 ` Eric Sunshine
2023-06-13 18:43 ` Jonathan Tan
2023-06-13 19:15 ` Eric Sunshine
2023-06-13 19:29 ` Junio C Hamano
2023-06-13 19:16 ` [PATCH v3 0/4] Changed path filter hash fix and version bump Junio C Hamano
2023-06-13 17:39 ` [PATCH v4 " Jonathan Tan
2023-06-13 17:39 ` [PATCH v4 1/4] gitformat-commit-graph: describe version 2 of BDAT Jonathan Tan
2023-06-13 21:58 ` Junio C Hamano
2023-06-20 13:22 ` Derrick Stolee
2023-06-21 12:08 ` Taylor Blau
2023-06-22 22:26 ` Jonathan Tan
2023-06-23 13:05 ` Derrick Stolee
2023-06-13 17:39 ` [PATCH v4 2/4] t4216: test changed path filters with high bit paths Jonathan Tan
2023-06-13 17:39 ` [PATCH v4 3/4] repo-settings: introduce commitgraph.changedPathsVersion Jonathan Tan
2023-06-20 13:28 ` Derrick Stolee
2023-06-21 12:14 ` Taylor Blau
2023-06-13 17:39 ` [PATCH v4 4/4] commit-graph: new filter ver. that fixes murmur3 Jonathan Tan
2023-06-20 13:39 ` Derrick Stolee [this message]
2023-06-20 18:37 ` Junio C Hamano
2023-06-13 19:21 ` [PATCH v4 0/4] Changed path filter hash fix and version bump Junio C Hamano
2023-06-20 13:43 ` Derrick Stolee
2023-06-20 21:56 ` Jonathan Tan
2023-06-21 12:19 ` Taylor Blau
2023-06-21 17:53 ` Derrick Stolee
2023-06-22 22:27 ` Jonathan Tan
2023-06-23 13:18 ` Derrick Stolee
2023-07-13 21:42 ` [PATCH v5 " Jonathan Tan
2023-07-13 21:42 ` [PATCH v5 1/4] gitformat-commit-graph: describe version 2 of BDAT Jonathan Tan
2023-07-19 17:25 ` Taylor Blau
2023-07-20 20:20 ` Jonathan Tan
2023-07-21 1:38 ` Taylor Blau
2023-07-13 21:42 ` [PATCH v5 2/4] t4216: test changed path filters with high bit paths Jonathan Tan
2023-07-13 22:50 ` Junio C Hamano
2023-07-19 17:27 ` Taylor Blau
2023-07-19 17:55 ` [PATCH 0/4] commit-graph: avoid looking at Bloom filter data directly Taylor Blau
2023-07-19 17:55 ` [PATCH 1/4] t/helper/test-read-graph.c: extract `dump_graph_info()` Taylor Blau
2023-07-19 17:55 ` [PATCH 2/4] bloom.h: make `load_bloom_filter_from_graph()` public Taylor Blau
2023-07-19 17:55 ` [PATCH 3/4] t/helper/test-read-graph: implement `bloom-filters` mode Taylor Blau
2023-07-19 17:55 ` [PATCH 4/4] fixup! t4216: test changed path filters with high bit paths Taylor Blau
2023-07-19 19:24 ` [PATCH 0/4] commit-graph: avoid looking at Bloom filter data directly Junio C Hamano
2023-07-20 20:22 ` Jonathan Tan
2023-07-13 21:42 ` [PATCH v5 3/4] repo-settings: introduce commitgraph.changedPathsVersion Jonathan Tan
2023-07-19 18:10 ` Taylor Blau
2023-07-20 20:42 ` Jonathan Tan
2023-07-20 21:02 ` Taylor Blau
2023-07-13 21:42 ` [PATCH v5 4/4] commit-graph: new filter ver. that fixes murmur3 Jonathan Tan
2023-07-19 18:24 ` Taylor Blau
2023-07-20 21:27 ` Jonathan Tan
2023-07-26 23:32 ` Taylor Blau
2023-07-13 22:16 ` [PATCH v5 0/4] Changed path filter hash fix and version bump Junio C Hamano
2023-07-13 22:59 ` Junio C Hamano
2023-07-14 18:48 ` Jonathan Tan
2023-07-20 21:46 ` [PATCH v6 0/7] " Jonathan Tan
2023-07-20 21:46 ` [PATCH v6 1/7] gitformat-commit-graph: describe version 2 of BDAT Jonathan Tan
2023-07-20 21:46 ` [PATCH v6 2/7] t/helper/test-read-graph.c: extract `dump_graph_info()` Jonathan Tan
2023-07-26 23:26 ` Taylor Blau
2023-07-20 21:46 ` [PATCH v6 3/7] bloom.h: make `load_bloom_filter_from_graph()` public Jonathan Tan
2023-07-20 21:46 ` [PATCH v6 4/7] t/helper/test-read-graph: implement `bloom-filters` mode Jonathan Tan
2023-07-20 21:46 ` [PATCH v6 5/7] t4216: test changed path filters with high bit paths Jonathan Tan
2023-07-26 23:28 ` Taylor Blau
2023-07-20 21:46 ` [PATCH v6 6/7] repo-settings: introduce commitgraph.changedPathsVersion Jonathan Tan
2023-07-20 21:46 ` [PATCH v6 7/7] commit-graph: new filter ver. that fixes murmur3 Jonathan Tan
2023-07-25 20:52 ` [PATCH v6 0/7] Changed path filter hash fix and version bump Junio C Hamano
2023-07-26 20:39 ` Junio C Hamano
2023-07-27 0:17 ` Taylor Blau
2023-07-27 0:49 ` Junio C Hamano
2023-07-27 17:39 ` Jonathan Tan
2023-07-27 17:56 ` Taylor Blau
2023-07-27 20:53 ` Jonathan Tan
2023-08-01 18:08 ` Taylor Blau
2023-08-01 18:52 ` Jonathan Tan
2023-08-03 0:01 ` Taylor Blau
2023-08-03 13:18 ` Derrick Stolee
2023-08-03 18:45 ` Taylor Blau
2023-07-27 18:44 ` Junio C Hamano
2023-08-01 18:41 ` [PATCH v7 " Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 1/7] gitformat-commit-graph: describe version 2 of BDAT Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 2/7] t/helper/test-read-graph.c: extract `dump_graph_info()` Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 3/7] bloom.h: make `load_bloom_filter_from_graph()` public Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 4/7] t/helper/test-read-graph: implement `bloom-filters` mode Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 5/7] t4216: test changed path filters with high bit paths Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 6/7] repo-settings: introduce commitgraph.changedPathsVersion Jonathan Tan
2023-08-01 18:41 ` [PATCH v7 7/7] commit-graph: new filter ver. that fixes murmur3 Jonathan Tan
2023-08-01 18:44 ` [PATCH v7 0/7] Changed path filter hash fix and version bump Junio C Hamano
2023-08-01 20:58 ` Taylor Blau
2023-08-01 21:07 ` Junio C Hamano
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4c5cadf2-bd70-c56e-3935-fb24b604f411@github.com \
--to=derrickstolee@github.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=jonathantanmy@google.com \
--cc=ramsay@ramsayjones.plus.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).