[07/15] commit-graph: new filter ver. that fixes murmur3

Commit Message

Taylor Blau Aug. 21, 2023, 9:44 p.m. UTC

From: Jonathan Tan <[e-mail]>

The murmur3 implementation in bloom.c has a bug when converting series
of 4 bytes into network-order integers when char is signed (which is
controllable by a compiler option, and the default signedness of char is
platform-specific). When a string contains characters with the high bit
set, this bug causes results that, although internally consistent within
Git, does not accord with other implementations of murmur3 (thus,
the changed path filters wouldn't be readable by other off-the-shelf
implementatios of murmur3) and even with Git binaries that were compiled
with different signedness of char. This bug affects both how Git writes
changed path filters to disk and how Git interprets changed path filters
on disk.

Therefore, introduce a new version (2) of changed path filters that
corrects this problem. The existing version (1) is still supported and
is still the default, but users should migrate away from it as soon
as possible.

Because this bug only manifests with characters that have the high bit
set, it may be possible that some (or all) commits in a given repo would
have the same changed path filter both before and after this fix is
applied. However, in order to determine whether this is the case, the
changed paths would first have to be computed, at which point it is not
much more expensive to just compute a new changed path filter.

So this patch does not include any mechanism to "salvage" changed path
filters from repositories. There is also no "mixed" mode - for each
invocation of Git, reading and writing changed path filters are done
with the same version number; this version number may be explicitly
stated (typically if the user knows which version they need) or
automatically determined from the version of the existing changed path
filters in the repository.

There is a change in write_commit_graph(). graph_read_bloom_data()
makes it possible for chunk_bloom_data to be non-NULL but
bloom_filter_settings to be NULL, which causes a segfault later on. I
produced such a segfault while developing this patch, but couldn't find
a way to reproduce it neither after this complete patch (or before),
but in any case it seemed like a good thing to include that might help
future patch authors.

The value in t0095 was obtained from another murmur3 implementation
using the following Go source code:

  package main

  import "fmt"
  import "github.com/spaolacci/murmur3"

  func main() {
          fmt.Printf("%x\n", murmur3.Sum32([]byte("Hello world!")))
          fmt.Printf("%x\n", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff}))
  }

Signed-off-by: Jonathan Tan <[e-mail]>
Signed-off-by: Junio C Hamano <[e-mail]>
Signed-off-by: Taylor Blau <[e-mail]>
---
 Documentation/config/commitgraph.txt |  5 +-
 bloom.c                              | 69 +++++++++++++++++++-
 bloom.h                              |  8 ++-
 commit-graph.c                       | 32 ++++++++--
 t/helper/test-bloom.c                |  9 ++-
 t/t0095-bloom.sh                     |  8 +++
 t/t4216-log-bloom.sh                 | 96 ++++++++++++++++++++++++++++
 7 files changed, 214 insertions(+), 13 deletions(-)

Comments

SZEDER Gábor Aug. 26, 2023, 3:06 p.m. UTC | #1

On Mon, Aug 21, 2023 at 05:44:15PM -0400, Taylor Blau wrote:
> From: Jonathan Tan <[e-mail]>
> 
> The murmur3 implementation in bloom.c has a bug when converting series
> of 4 bytes into network-order integers when char is signed (which is
> controllable by a compiler option, and the default signedness of char is
> platform-specific). When a string contains characters with the high bit
> set, this bug causes results that, although internally consistent within
> Git, does not accord with other implementations of murmur3 (thus,
> the changed path filters wouldn't be readable by other off-the-shelf
> implementatios of murmur3) and even with Git binaries that were compiled
> with different signedness of char. This bug affects both how Git writes
> changed path filters to disk and how Git interprets changed path filters
> on disk.
> 
> Therefore, introduce a new version (2) of changed path filters that
> corrects this problem. The existing version (1) is still supported and
> is still the default, but users should migrate away from it as soon
> as possible.
> 
> Because this bug only manifests with characters that have the high bit
> set, it may be possible that some (or all) commits in a given repo would
> have the same changed path filter both before and after this fix is
> applied. However, in order to determine whether this is the case, the
> changed paths would first have to be computed, at which point it is not
> much more expensive to just compute a new changed path filter.
> 
> So this patch does not include any mechanism to "salvage" changed path
> filters from repositories. There is also no "mixed" mode - for each
> invocation of Git, reading and writing changed path filters are done
> with the same version number; this version number may be explicitly
> stated (typically if the user knows which version they need) or
> automatically determined from the version of the existing changed path
> filters in the repository.
> 
> There is a change in write_commit_graph(). graph_read_bloom_data()
> makes it possible for chunk_bloom_data to be non-NULL but
> bloom_filter_settings to be NULL, which causes a segfault later on. I
> produced such a segfault while developing this patch, but couldn't find
> a way to reproduce it neither after this complete patch (or before),
> but in any case it seemed like a good thing to include that might help
> future patch authors.
> 
> The value in t0095 was obtained from another murmur3 implementation
> using the following Go source code:
> 
>   package main
> 
>   import "fmt"
>   import "github.com/spaolacci/murmur3"
> 
>   func main() {
>           fmt.Printf("%x\n", murmur3.Sum32([]byte("Hello world!")))
>           fmt.Printf("%x\n", murmur3.Sum32([]byte{0x99, 0xaa, 0xbb, 0xcc, 0xdd, 0xee, 0xff}))
>   }
> 
> Signed-off-by: Jonathan Tan <[e-mail]>
> Signed-off-by: Junio C Hamano <[e-mail]>
> Signed-off-by: Taylor Blau <[e-mail]>
> ---
>  Documentation/config/commitgraph.txt |  5 +-
>  bloom.c                              | 69 +++++++++++++++++++-
>  bloom.h                              |  8 ++-
>  commit-graph.c                       | 32 ++++++++--
>  t/helper/test-bloom.c                |  9 ++-
>  t/t0095-bloom.sh                     |  8 +++
>  t/t4216-log-bloom.sh                 | 96 ++++++++++++++++++++++++++++
>  7 files changed, 214 insertions(+), 13 deletions(-)
> 
> diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt
> index 2dc9170622..acc74a2f27 100644
> --- a/Documentation/config/commitgraph.txt
> +++ b/Documentation/config/commitgraph.txt
> @@ -15,7 +15,7 @@ commitGraph.readChangedPaths::
>  
>  commitGraph.changedPathsVersion::
>  	Specifies the version of the changed-path Bloom filters that Git will read and
> -	write. May be -1, 0 or 1.
> +	write. May be -1, 0, 1, or 2.
>  +
>  Defaults to -1.
>  +
> @@ -28,4 +28,7 @@ filters when instructed to write.
>  If 1, Git will only read version 1 Bloom filters, and will write version 1
>  Bloom filters.
>  +
> +If 2, Git will only read version 2 Bloom filters, and will write version 2
> +Bloom filters.
> ++
>  See linkgit:git-commit-graph[1] for more information.
> diff --git a/bloom.c b/bloom.c
> index 3e78cfe79d..ebef5cfd2f 100644
> --- a/bloom.c
> +++ b/bloom.c
> @@ -66,7 +66,64 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
>   * Not considered to be cryptographically secure.
>   * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
>   */
> -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
> +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)

Nit: MurmurHash3 implementations in C/C++ (apart from the sample
implementation on Wikipedia), and other hash functions taking data
pointer and buffer size parameters in general, have a 'const void
*data' parameter, not 'const char*'.

> +{
> +	const uint32_t c1 = 0xcc9e2d51;
> +	const uint32_t c2 = 0x1b873593;
> +	const uint32_t r1 = 15;
> +	const uint32_t r2 = 13;
> +	const uint32_t m = 5;
> +	const uint32_t n = 0xe6546b64;
> +	int i;
> +	uint32_t k1 = 0;
> +	const char *tail;
> +
> +	int len4 = len / sizeof(uint32_t);
> +
> +	uint32_t k;
> +	for (i = 0; i < len4; i++) {
> +		uint32_t byte1 = (uint32_t)(unsigned char)data[4*i];
> +		uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8;
> +		uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16;
> +		uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24;
> +		k = byte1 | byte2 | byte3 | byte4;
> +		k *= c1;
> +		k = rotate_left(k, r1);
> +		k *= c2;
> +
> +		seed ^= k;
> +		seed = rotate_left(seed, r2) * m + n;
> +	}
> +
> +	tail = (data + len4 * sizeof(uint32_t));
> +
> +	switch (len & (sizeof(uint32_t) - 1)) {
> +	case 3:
> +		k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16;
> +		/*-fallthrough*/
> +	case 2:
> +		k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8;
> +		/*-fallthrough*/
> +	case 1:
> +		k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0;
> +		k1 *= c1;
> +		k1 = rotate_left(k1, r1);
> +		k1 *= c2;
> +		seed ^= k1;
> +		break;
> +	}
> +
> +	seed ^= (uint32_t)len;
> +	seed ^= (seed >> 16);
> +	seed *= 0x85ebca6b;
> +	seed ^= (seed >> 13);
> +	seed *= 0xc2b2ae35;
> +	seed ^= (seed >> 16);
> +
> +	return seed;
> +}
> +
> +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;
> @@ -131,8 +188,14 @@ 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);
> +	uint32_t hash0, hash1;
> +	if (settings->hash_version == 2) {
> +		hash0 = murmur3_seeded_v2(seed0, data, len);
> +		hash1 = murmur3_seeded_v2(seed1, data, len);
> +	} else {
> +		hash0 = murmur3_seeded_v1(seed0, data, len);
> +		hash1 = murmur3_seeded_v1(seed1, data, len);
> +	}
>  
>  	key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
>  	for (i = 0; i < settings->num_hashes; i++)
> diff --git a/bloom.h b/bloom.h
> index 1e4f612d2c..138d57a86b 100644
> --- a/bloom.h
> +++ b/bloom.h
> @@ -8,9 +8,11 @@ struct commit_graph;
>  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.
>  	 */
>  	uint32_t hash_version;
>  
> @@ -80,7 +82,7 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
>   * Not considered to be cryptographically secure.
>   * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
>   */
> -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);
> +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len);
>  
>  void fill_bloom_key(const char *data,
>  		    size_t len,
> diff --git a/commit-graph.c b/commit-graph.c
> index da99f15fdf..f7322c4fff 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -304,17 +304,26 @@ static int graph_read_oid_lookup(const unsigned char *chunk_start,
>  	return 0;
>  }
>  
> +struct graph_read_bloom_data_context {
> +	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_context *c = data;
> +	struct commit_graph *g = c->g;
>  	uint32_t hash_version;
> -	g->chunk_bloom_data = chunk_start;
>  	hash_version = get_be32(chunk_start);
>  
> -	if (hash_version != 1)
> +	if (*c->commit_graph_changed_paths_version == -1) {
> +		*c->commit_graph_changed_paths_version = hash_version;
> +	} else if (hash_version != *c->commit_graph_changed_paths_version) {
>  		return 0;
> +	}
>  
> +	g->chunk_bloom_data = chunk_start;
>  	g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
>  	g->bloom_filter_settings->hash_version = hash_version;
>  	g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);
> @@ -402,10 +411,14 @@ struct commit_graph *parse_commit_graph(struct repo_settings *s,
>  	}
>  
>  	if (s->commit_graph_changed_paths_version) {
> +		struct graph_read_bloom_data_context context = {
> +			.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, &context);
>  	}
>  
>  	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
> @@ -2376,6 +2389,13 @@ int write_commit_graph(struct object_directory *odb,
>  	}
>  	if (!commit_graph_compatible(r))
>  		return 0;
> +	if (r->settings.commit_graph_changed_paths_version < -1
> +	    || 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;
> +	}
>  
>  	CALLOC_ARRAY(ctx, 1);
>  	ctx->r = r;
> @@ -2388,6 +2408,8 @@ int write_commit_graph(struct object_directory *odb,
>  	ctx->write_generation_data = (get_configured_generation_version(r) == 2);
>  	ctx->num_generation_data_overflows = 0;
>  
> +	bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2
> +		? 2 : 1;
>  	bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
>  						      bloom_settings.bits_per_entry);
>  	bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
> @@ -2417,7 +2439,7 @@ int write_commit_graph(struct object_directory *odb,
>  		g = ctx->r->objects->commit_graph;
>  
>  		/* 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;
>  		}
> diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
> index aabe31d724..3cbc0a5b50 100644
> --- a/t/helper/test-bloom.c
> +++ b/t/helper/test-bloom.c
> @@ -50,6 +50,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
>  
>  static const char *bloom_usage = "\n"
>  "  test-tool bloom get_murmur3 <string>\n"
> +"  test-tool bloom get_murmur3_seven_highbit\n"
>  "  test-tool bloom generate_filter <string> [<string>...]\n"
>  "  test-tool bloom get_filter_for_commit <commit-hex>\n";
>  
> @@ -64,7 +65,13 @@ int cmd__bloom(int argc, const char **argv)
>  		uint32_t hashed;
>  		if (argc < 3)
>  			usage(bloom_usage);
> -		hashed = murmur3_seeded(0, argv[2], strlen(argv[2]));
> +		hashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2]));
> +		printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
> +	}
> +
> +	if (!strcmp(argv[1], "get_murmur3_seven_highbit")) {
> +		uint32_t hashed;
> +		hashed = murmur3_seeded_v2(0, "\x99\xaa\xbb\xcc\xdd\xee\xff", 7);
>  		printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
>  	}
>  
> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh
> index b567383eb8..c8d84ab606 100755
> --- a/t/t0095-bloom.sh
> +++ b/t/t0095-bloom.sh
> @@ -29,6 +29,14 @@ test_expect_success 'compute unseeded murmur3 hash for test string 2' '
>  	test_cmp expect actual
>  '
>  
> +test_expect_success 'compute unseeded murmur3 hash for test string 3' '
> +	cat >expect <<-\EOF &&
> +	Murmur3 Hash with seed=0:0xa183ccfd
> +	EOF
> +	test-tool bloom get_murmur3_seven_highbit >actual &&
> +	test_cmp expect actual
> +'
> +
>  test_expect_success 'compute bloom key for empty string' '
>  	cat >expect <<-\EOF &&
>  	Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|
> diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
> index 2d4a3fefee..775e59d864 100755
> --- a/t/t4216-log-bloom.sh
> +++ b/t/t4216-log-bloom.sh
> @@ -447,4 +447,100 @@ test_expect_success 'version 1 changed-path used when version 1 requested' '
>  	)
>  '
>  
> +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"
> +	)
> +'
> +
> +test_expect_success 'version 1 changed-path used when autodetect requested' '
> +	(
> +		cd highbit1 &&
> +		git config --add commitgraph.changedPathsVersion -1 &&
> +		test_bloom_filters_used "-- $CENT"
> +	)
> +'
> +
> +test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '
> +	test_commit -C highbit1 c1double "$CENT$CENT" &&
> +	git -C highbit1 commit-graph write --reachable --changed-paths &&

Nit: Since there is a subshell cd-ing into the 'highbit1' directory
anyway, it would look clearer to put these two commands into that
subshell as well.
This applies to some of the later test cases as well.

> +	(
> +		cd highbit1 &&
> +		git config --add commitgraph.changedPathsVersion -1 &&
> +		echo "options: bloom(1,10,7) read_generation_data" >expect &&
> +		test-tool read-graph >full &&
> +		grep options full >actual &&
> +		test_cmp expect actual
> +	)
> +'
> +
> +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 &&
> +		echo "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"

This test_bloom_filter_used helper runs two pathspec-limited 'git log'
invocations, one with disabled and the other with enabled
commit-graph, and thus with disabled and enabled modified path Bloom
filters, and compares their output.

One of the flaws of the current modified path Bloom filters
implementation is that it doesn't check Bloom filters for root
commits.

In several of the above test cases test_bloom_filters_used is invoked
in a repository with only a root commit, so they don't check that
the output is the same with and without Bloom filters.

> +	)
> +'
> +
> +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"
> +	)
> +'
> +
> +test_expect_success 'version 2 changed-path used when autodetect requested' '
> +	(
> +		cd highbit2 &&
> +		git config --add commitgraph.changedPathsVersion -1 &&
> +		test_bloom_filters_used "-- $CENT"
> +	)
> +'
> +
> +test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' '
> +	test_commit -C highbit2 c2double "$CENT$CENT" &&
> +	git -C highbit2 commit-graph write --reachable --changed-paths &&
> +	(
> +		cd highbit2 &&
> +		git config --add commitgraph.changedPathsVersion -1 &&
> +		echo "options: bloom(2,10,7) read_generation_data" >expect &&
> +		test-tool read-graph >full &&
> +		grep options full >actual &&
> +		test_cmp expect actual
> +	)
> +'
> +
> +test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '
> +	git init doublewrite &&
> +	test_commit -C doublewrite c "$CENT" &&
> +	git -C doublewrite config --add commitgraph.changedPathsVersion 1 &&
> +	git -C doublewrite commit-graph write --reachable --changed-paths &&
> +	git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
> +	git -C doublewrite commit-graph write --reachable --changed-paths &&
> +	(
> +		cd doublewrite &&
> +		echo "c01f" >expect &&
> +		get_first_changed_path_filter >actual &&
> +		test_cmp expect actual
> +	)
> +'

The string "split" occurs twice in this patch series, but only in
patch hunk contexts, and it doesn't occur at all in the previous long
thread about the original patch series.

Unfortunately, split commit-graphs weren't really considered in the
design of the modified path Bloom filters feature, and layers with
different Bloom filter settings weren't considered at all.  I've
reported it back then, but the fixes so far were incomplete, and e.g.
the test cases shown in

  https://public-inbox.org/git/[e-mail]/

still fail.

Since the interaction of different versions and split commit-graphs
was neither mentioned in any of the commit messages nor discussed
during the previous rounds, and there isn't any test case excercising
it, and since the Bloom filter version information is stored in the
same 'g->bloom_filter_settings' structure as the number of hashes, I'm
afraid (though haven't actually checked) that handling commit-graph
layers with different Bloom filter versions is prone to the same
issues as well.

Jonathan Tan Aug. 29, 2023, 4:31 p.m. UTC | #2

SZEDER Gábor <[e-mail]> writes:
> > @@ -66,7 +66,64 @@ int load_bloom_filter_from_graph(struct commit_graph *g,
> >   * Not considered to be cryptographically secure.
> >   * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
> >   */
> > -uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
> > +uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)
> 
> Nit: MurmurHash3 implementations in C/C++ (apart from the sample
> implementation on Wikipedia), and other hash functions taking data
> pointer and buffer size parameters in general, have a 'const void
> *data' parameter, not 'const char*'.

I think either works, so I'll stick with what the existing code uses.
(Well, we probably should have used "unsigned char" in the first place.)

> > +test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '
> > +	test_commit -C highbit1 c1double "$CENT$CENT" &&
> > +	git -C highbit1 commit-graph write --reachable --changed-paths &&
> 
> Nit: Since there is a subshell cd-ing into the 'highbit1' directory
> anyway, it would look clearer to put these two commands into that
> subshell as well.
> This applies to some of the later test cases as well.

Makes sense, but this patch series has already been reviewed a few times
so I don't think it's worth making this change at this point in the
review process for a small increase in readability.

> > +test_expect_success 'version 2 changed-path used when version 2 requested' '
> > +	(
> > +		cd highbit2 &&
> > +		test_bloom_filters_used "-- $CENT"
> 
> This test_bloom_filter_used helper runs two pathspec-limited 'git log'
> invocations, one with disabled and the other with enabled
> commit-graph, and thus with disabled and enabled modified path Bloom
> filters, and compares their output.
> 
> One of the flaws of the current modified path Bloom filters
> implementation is that it doesn't check Bloom filters for root
> commits.
> 
> In several of the above test cases test_bloom_filters_used is invoked
> in a repository with only a root commit, so they don't check that
> the output is the same with and without Bloom filters.

Ah...you are right. Indeed, when I flip one of the tests from
test_bloom_filters_used to _not_, the test still passes. I'll change
the tests.

> The string "split" occurs twice in this patch series, but only in
> patch hunk contexts, and it doesn't occur at all in the previous long
> thread about the original patch series.
> 
> Unfortunately, split commit-graphs weren't really considered in the
> design of the modified path Bloom filters feature, and layers with
> different Bloom filter settings weren't considered at all.  I've
> reported it back then, but the fixes so far were incomplete, and e.g.
> the test cases shown in
> 
>   https://public-inbox.org/git/[e-mail]/
> 
> still fail.
> 
> Since the interaction of different versions and split commit-graphs
> was neither mentioned in any of the commit messages nor discussed
> during the previous rounds, and there isn't any test case excercising
> it, and since the Bloom filter version information is stored in the
> same 'g->bloom_filter_settings' structure as the number of hashes, I'm
> afraid (though haven't actually checked) that handling commit-graph
> layers with different Bloom filter versions is prone to the same
> issues as well.

My original design (up to patch 7 in this patch set) defends against
this by taking the very first version detected and rejecting every
other version, and Taylor's subsequent design reads every version, but
annotates filters with its version. So I think we're covered.

SZEDER Gábor Aug. 30, 2023, 8:02 p.m. UTC | #3

On Tue, Aug 29, 2023 at 09:31:23AM -0700, Jonathan Tan wrote:
> SZEDER Gábor <[e-mail]> writes:
 
> > > +test_expect_success 'version 2 changed-path used when version 2 requested' '
> > > +	(
> > > +		cd highbit2 &&
> > > +		test_bloom_filters_used "-- $CENT"
> > 
> > This test_bloom_filter_used helper runs two pathspec-limited 'git log'
> > invocations, one with disabled and the other with enabled
> > commit-graph, and thus with disabled and enabled modified path Bloom
> > filters, and compares their output.
> > 
> > One of the flaws of the current modified path Bloom filters
> > implementation is that it doesn't check Bloom filters for root
> > commits.
> > 
> > In several of the above test cases test_bloom_filters_used is invoked
> > in a repository with only a root commit, so they don't check that
> > the output is the same with and without Bloom filters.
> 
> Ah...you are right. Indeed, when I flip one of the tests from
> test_bloom_filters_used to _not_, the test still passes. I'll change
> the tests.

I'd prefer to leave the test cases unchanged, and make the revision
walking machinery look at Bloom filters even for root commits, because
this is an annoying and recurring testing issue.  I remember it
annoyed me back then, when I wanted to reproduce a couple of bugs that
I knew were there, but my initial test cases didn't fail because the
Bloom filter of the root commit was ignored; Derrick overlooked this
in b16a8277644, you overlooked it now, and none of the reviewers then
and now caught it, either.

> > The string "split" occurs twice in this patch series, but only in
> > patch hunk contexts, and it doesn't occur at all in the previous long
> > thread about the original patch series.
> > 
> > Unfortunately, split commit-graphs weren't really considered in the
> > design of the modified path Bloom filters feature, and layers with
> > different Bloom filter settings weren't considered at all.  I've
> > reported it back then, but the fixes so far were incomplete, and e.g.
> > the test cases shown in
> > 
> >   https://public-inbox.org/git/[e-mail]/
> > 
> > still fail.
> > 
> > Since the interaction of different versions and split commit-graphs
> > was neither mentioned in any of the commit messages nor discussed
> > during the previous rounds, and there isn't any test case excercising
> > it, and since the Bloom filter version information is stored in the
> > same 'g->bloom_filter_settings' structure as the number of hashes, I'm
> > afraid (though haven't actually checked) that handling commit-graph
> > layers with different Bloom filter versions is prone to the same
> > issues as well.
> 
> My original design (up to patch 7 in this patch set) defends against
> this by taking the very first version detected and rejecting every
> other version, and Taylor's subsequent design reads every version, but
> annotates filters with its version. So I think we're covered.

In the meantime I adapted the test cases from the above linked message
to write commit-graph layers with different Bloom filter versions, and
it does fail, because commits from the bottom commit-graph layer are
omitted from the revision walk's output.  And the test case doesn't
even need a middle layer without modified path Bloom filters to "hide"
the different version in the bottom layer.  Merging the layers seems
to work, though.

Besides fixing this issue, I think that the interaction of different
Bloom filter versions and split commit-graphs needs to be thoroughly
covered with test cases and discussed in the commit messages before
this series could be considered good for merging.


diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 48f8109a66..55f67e5110 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -586,4 +586,40 @@ test_expect_success 'when writing commit graph, reuse changed-path of another ve
 	test_filter_upgraded 1 trace2.txt
 '
 
+test_expect_success 'split commit graph vs changed paths breakage - setup' '
+	git init split-breakage &&
+	(
+		cd split-breakage &&
+		git commit --allow-empty -m "Bloom filters are written but still ignored for root commits :(" &&
+		for i in 1 2 3
+		do
+			echo $i >$CENT &&
+			git add $CENT &&
+			git commit -m "$i" || return 1
+		done &&
+		git log --oneline -- $CENT >expect
+	)
+'
+
+test_expect_failure 'split commit graph vs changed paths breakage - split' '
+	(
+		cd split-breakage &&
+
+		# Compute v1 Bloom filters for the commits at the bottom.
+		git rev-parse HEAD^ | git commit-graph write --stdin-commits --changed-paths --split &&
+		# Compute v2 Bloom filters for the rest of the commits at the top.
+		git rev-parse HEAD | git -c commitgraph.changedPathsVersion=2 commit-graph write --stdin-commits --changed-paths --split=no-merge &&
+
+		# Just to make sure that there are as many graph layers as I
+		# think there should be.
+		test_line_count = 2 .git/objects/info/commit-graphs/commit-graph-chain &&
+
+		# This checks Bloom filters using version information in the
+		# top layer, thus misses commits modifying the file in the
+		# bottom commit-graph layer.
+		git log --oneline -- $CENT >actual &&
+		test_cmp expect actual
+	)
+'
+
 test_done

It fails with:

  + cd split-breakage
  + git rev-parse HEAD^
  + git commit-graph write --stdin-commits --changed-paths --split
  + git rev-parse HEAD
  + git -c commitgraph.changedPathsVersion=2 commit-graph write --stdin-commits --changed-paths --split=no-merge
  + test_line_count = 2 .git/objects/info/commit-graphs/commit-graph-chain
  + git log --oneline -- ¢
  + test_cmp expect actual
  --- expect      2023-08-30 19:07:59.882066827 +0000
  +++ actual      2023-08-30 19:07:59.894067148 +0000
  @@ -1,3 +1 @@
   1db2248 3
  -cfcc97f 2
  -bd9c2c8 1
  error: last command exited with $?=1

Jonathan Tan Sept. 1, 2023, 8:56 p.m. UTC | #4

SZEDER Gábor <[e-mail]> writes:
> I'd prefer to leave the test cases unchanged, and make the revision
> walking machinery look at Bloom filters even for root commits, because
> this is an annoying and recurring testing issue.  I remember it
> annoyed me back then, when I wanted to reproduce a couple of bugs that
> I knew were there, but my initial test cases didn't fail because the
> Bloom filter of the root commit was ignored; Derrick overlooked this
> in b16a8277644, you overlooked it now, and none of the reviewers then
> and now caught it, either.

I agree that making the revwalk look at Bloom filters of root commits
is an urgent matter for the reasons you describe (it's something
easily missed that slows down future development and/or makes future
development error-prone), but so is moving to a correct murmur3
implementation, I think, and one shouldn't stop the other. There could
be an argument that because the revwalk doesn't look at root commit
Bloom filters, any development on a new Bloom filter hash version is
suspect, but I don't think that has to be completely true.

> > My original design (up to patch 7 in this patch set) defends against
> > this by taking the very first version detected and rejecting every
> > other version, and Taylor's subsequent design reads every version, but
> > annotates filters with its version. So I think we're covered.
> 
> In the meantime I adapted the test cases from the above linked message
> to write commit-graph layers with different Bloom filter versions, and
> it does fail, because commits from the bottom commit-graph layer are
> omitted from the revision walk's output.  And the test case doesn't
> even need a middle layer without modified path Bloom filters to "hide"
> the different version in the bottom layer.  Merging the layers seems
> to work, though.

For what it's worth, your test case below (with test_expect_success
instead of test_expect_failure) passes with my original design. With the
full patch set, it does fail, but for what it's worth, I did spot this,
providing an incomplete solution [1] and then a complete one [2]. Your
test case passes if I also include the following:

  diff --git a/bloom.c b/bloom.c
  index ff131893cd..1bafd62a4e 100644
  --- a/bloom.c
  +++ b/bloom.c
  @@ -344,6 +344,10 @@ struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
   
          prepare_repo_settings(r);
          hash_version = r->settings.commit_graph_changed_paths_version;
  +       if (hash_version == -1) {
  +               struct bloom_filter_settings *s = get_bloom_filter_settings(r);
  +               hash_version = (s && s->hash_version == 2) ? 2 : 1;
  +       }
   
          if (!(hash_version == -1 || hash_version == filter->version))
                  return NULL; /* unusable filter */

[1] https://lore.kernel.org/git/[e-mail]/
[2] https://lore.kernel.org/git/[e-mail]/

> Besides fixing this issue, I think that the interaction of different
> Bloom filter versions and split commit-graphs needs to be thoroughly
> covered with test cases and discussed in the commit messages before
> this series could be considered good for merging.

Regarding commit messages, I can see that in "commit-graph: new filter
ver. that fixes murmur3", I could add "(the first version read if there
are multiple versions of changed path filters in the repository)" after
"automatically determined from the version of the existing changed path
filters in the repository". Taylor's patches already inherently cover
multiple versions, I think, since Bloom filters are annotated with their
versions, individually.

Regarding tests, yes, we could add the one you provided.

If you (or anyone else) can spot anything else that should be added,
please let us know.

Taylor Blau Sept. 25, 2023, 11:03 p.m. UTC | #5

On Fri, Sep 01, 2023 at 01:56:15PM -0700, Jonathan Tan wrote:
> > > My original design (up to patch 7 in this patch set) defends against
> > > this by taking the very first version detected and rejecting every
> > > other version, and Taylor's subsequent design reads every version, but
> > > annotates filters with its version. So I think we're covered.
> >
> > In the meantime I adapted the test cases from the above linked message
> > to write commit-graph layers with different Bloom filter versions, and
> > it does fail, because commits from the bottom commit-graph layer are
> > omitted from the revision walk's output.  And the test case doesn't
> > even need a middle layer without modified path Bloom filters to "hide"
> > the different version in the bottom layer.  Merging the layers seems
> > to work, though.
>
> For what it's worth, your test case below (with test_expect_success
> instead of test_expect_failure) passes with my original design. With the
> full patch set, it does fail, but for what it's worth, I did spot this,
> providing an incomplete solution [1] and then a complete one [2]. Your
> test case passes if I also include the following:
>
>   diff --git a/bloom.c b/bloom.c
>   index ff131893cd..1bafd62a4e 100644
>   --- a/bloom.c
>   +++ b/bloom.c
>   @@ -344,6 +344,10 @@ struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
>
>           prepare_repo_settings(r);
>           hash_version = r->settings.commit_graph_changed_paths_version;
>   +       if (hash_version == -1) {
>   +               struct bloom_filter_settings *s = get_bloom_filter_settings(r);
>   +               hash_version = (s && s->hash_version == 2) ? 2 : 1;
>   +       }
>
>           if (!(hash_version == -1 || hash_version == filter->version))
>                   return NULL; /* unusable filter */
>
> [1] https://lore.kernel.org/git/[e-mail]/
> [2] https://lore.kernel.org/git/[e-mail]/

Hmm. I am confused -- are you saying that this series breaks existing
functionality, or merely does not patch an existing breakage? I *think*
that it's the latter, since this test case fails identically on master,
but I am not sure.

If my understanding is correct, I think that patching this would involve
annotating each Bloom filter with a pointer to the bloom_filter_settings
it was written with, and then using those settings when querying it.

Thanks,
Taylor

SZEDER Gábor Oct. 8, 2023, 2:35 p.m. UTC | #6

On Mon, Sep 25, 2023 at 07:03:18PM -0400, Taylor Blau wrote:
> On Fri, Sep 01, 2023 at 01:56:15PM -0700, Jonathan Tan wrote:
> > > > My original design (up to patch 7 in this patch set) defends against
> > > > this by taking the very first version detected and rejecting every
> > > > other version, and Taylor's subsequent design reads every version, but
> > > > annotates filters with its version. So I think we're covered.
> > >
> > > In the meantime I adapted the test cases from the above linked message
> > > to write commit-graph layers with different Bloom filter versions, and
> > > it does fail, because commits from the bottom commit-graph layer are
> > > omitted from the revision walk's output.  And the test case doesn't
> > > even need a middle layer without modified path Bloom filters to "hide"
> > > the different version in the bottom layer.  Merging the layers seems
> > > to work, though.
> >
> > For what it's worth, your test case below (with test_expect_success
> > instead of test_expect_failure) passes with my original design. With the
> > full patch set, it does fail, but for what it's worth, I did spot this,
> > providing an incomplete solution [1] and then a complete one [2]. Your
> > test case passes if I also include the following:
> >
> >   diff --git a/bloom.c b/bloom.c
> >   index ff131893cd..1bafd62a4e 100644
> >   --- a/bloom.c
> >   +++ b/bloom.c
> >   @@ -344,6 +344,10 @@ struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
> >
> >           prepare_repo_settings(r);
> >           hash_version = r->settings.commit_graph_changed_paths_version;
> >   +       if (hash_version == -1) {
> >   +               struct bloom_filter_settings *s = get_bloom_filter_settings(r);
> >   +               hash_version = (s && s->hash_version == 2) ? 2 : 1;
> >   +       }
> >
> >           if (!(hash_version == -1 || hash_version == filter->version))
> >                   return NULL; /* unusable filter */
> >
> > [1] https://lore.kernel.org/git/[e-mail]/
> > [2] https://lore.kernel.org/git/[e-mail]/
> 
> Hmm. I am confused -- are you saying that this series breaks existing
> functionality, or merely does not patch an existing breakage? I *think*
> that it's the latter,

It's neither: the new functionality added in this series is broken.

> since this test case fails identically on master,
> but I am not sure.

Not sure what test you are referring to.  My test demonstrating the
breakage succeeds when adaped to master, because master doesn't
understand the commitgraph.changedPathsVersion=2 setting, and keeps
writing v1 Bloom filter chunks instead, so all commit-graphs layers
contain the same version.

> If my understanding is correct, I think that patching this would involve
> annotating each Bloom filter with a pointer to the bloom_filter_settings
> it was written with, and then using those settings when querying it.

In general we are better off when we don't write Bloom filter chunks
with different settings in the first place.

Taylor Blau Oct. 9, 2023, 6:17 p.m. UTC | #7

On Sun, Oct 08, 2023 at 04:35:23PM +0200, SZEDER Gábor wrote:
> > Hmm. I am confused -- are you saying that this series breaks existing
> > functionality, or merely does not patch an existing breakage? I *think*
> > that it's the latter,
>
> It's neither: the new functionality added in this series is broken.
>
> > since this test case fails identically on master,
> > but I am not sure.
>
> Not sure what test you are referring to.  My test demonstrating the
> breakage succeeds when adaped to master, because master doesn't
> understand the commitgraph.changedPathsVersion=2 setting, and keeps
> writing v1 Bloom filter chunks instead, so all commit-graphs layers
> contain the same version.

I was referring to the test you sent back in:

    https://public-inbox.org/git/[e-mail]/

but I think that I should have been looking at the one you sent more
recently in:

    https://lore.kernel.org/git/[e-mail]/

Thanks,
Taylor

Taylor Blau Oct. 9, 2023, 7:31 p.m. UTC | #8

On Mon, Oct 09, 2023 at 02:17:54PM -0400, Taylor Blau wrote:
> On Sun, Oct 08, 2023 at 04:35:23PM +0200, SZEDER Gábor wrote:
> > > Hmm. I am confused -- are you saying that this series breaks existing
> > > functionality, or merely does not patch an existing breakage? I *think*
> > > that it's the latter,
> >
> > It's neither: the new functionality added in this series is broken.
> >
> > > since this test case fails identically on master,
> > > but I am not sure.
> >
> > Not sure what test you are referring to.  My test demonstrating the
> > breakage succeeds when adaped to master, because master doesn't
> > understand the commitgraph.changedPathsVersion=2 setting, and keeps
> > writing v1 Bloom filter chunks instead, so all commit-graphs layers
> > contain the same version.
>
> I was referring to the test you sent back in:
>
>     https://public-inbox.org/git/[e-mail]/
>
> but I think that I should have been looking at the one you sent more
> recently in:
>
>     https://lore.kernel.org/git/[e-mail]/

OK, I think that I now have my head wrapped around what you're saying.

However, I am not entirely sure I agree with you that this is a "new"
issue. At least in the sense that Git (on 'master') does not currently
know how to deal with Bloom filters that have different settings across
commit-graph layers.

IOW, you could produce this problem today using the test you wrote in
<[e-mail]> using different values of the
GIT_BLOOM_SETTINGS environment variables as a proxy for different values
of the commitGraph.changedPathsVersion configuration variable introduced
in this series.

So I think that this series makes it easier to fall into that trap, but
the trap itself is not new. I think a reasonable stopgap (which IIUC you
have suggested earlier) is to prevent writing a new commit-graph layer
with a different hash version than the previous layer.

How does that sound?

Thanks,
Taylor

Junio C Hamano Oct. 9, 2023, 7:52 p.m. UTC | #9

Taylor Blau <[e-mail]> writes:

> However, I am not entirely sure I agree with you that this is a "new"
> issue. At least in the sense that Git (on 'master') does not currently
> know how to deal with Bloom filters that have different settings across
> commit-graph layers.
>
> IOW, you could produce this problem today using the test you wrote in
> <[e-mail]> using different values of the
> GIT_BLOOM_SETTINGS environment variables as a proxy for different values
> of the commitGraph.changedPathsVersion configuration variable introduced
> in this series.
>
> So I think that this series makes it easier to fall into that trap, but
> the trap itself is not new. I think a reasonable stopgap (which IIUC you
> have suggested earlier) is to prevent writing a new commit-graph layer
> with a different hash version than the previous layer.

What we probably want more urgently than that stopgap is to perhaps
teach the code pretend as if commit-graph did not exist when we
detect multiple layers use different hash versions (or perhaps only
use the base layer and ignore the rest as an anti-pessimization), to
protect correctness first, no?

Taylor Blau Oct. 10, 2023, 8:34 p.m. UTC | #10

On Mon, Oct 09, 2023 at 12:52:13PM -0700, Junio C Hamano wrote:
> Taylor Blau <[e-mail]> writes:
>
> > However, I am not entirely sure I agree with you that this is a "new"
> > issue. At least in the sense that Git (on 'master') does not currently
> > know how to deal with Bloom filters that have different settings across
> > commit-graph layers.
> >
> > IOW, you could produce this problem today using the test you wrote in
> > <[e-mail]> using different values of the
> > GIT_BLOOM_SETTINGS environment variables as a proxy for different values
> > of the commitGraph.changedPathsVersion configuration variable introduced
> > in this series.
> >
> > So I think that this series makes it easier to fall into that trap, but
> > the trap itself is not new. I think a reasonable stopgap (which IIUC you
> > have suggested earlier) is to prevent writing a new commit-graph layer
> > with a different hash version than the previous layer.
>
> What we probably want more urgently than that stopgap is to perhaps
> teach the code pretend as if commit-graph did not exist when we
> detect multiple layers use different hash versions (or perhaps only
> use the base layer and ignore the rest as an anti-pessimization), to
> protect correctness first, no?

Very good suggestion, thanks.

Thanks,
Taylor

Patch

diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt
index 2dc9170622..acc74a2f27 100644
--- a/Documentation/config/commitgraph.txt
+++ b/Documentation/config/commitgraph.txt
@@ -15,7 +15,7 @@  commitGraph.readChangedPaths::
 
 commitGraph.changedPathsVersion::
 	Specifies the version of the changed-path Bloom filters that Git will read and
-	write. May be -1, 0 or 1.
+	write. May be -1, 0, 1, or 2.
 +
 Defaults to -1.
 +
@@ -28,4 +28,7 @@  filters when instructed to write.
 If 1, Git will only read version 1 Bloom filters, and will write version 1
 Bloom filters.
 +
+If 2, Git will only read version 2 Bloom filters, and will write version 2
+Bloom filters.
++
 See linkgit:git-commit-graph[1] for more information.
diff --git a/bloom.c b/bloom.c
index 3e78cfe79d..ebef5cfd2f 100644
--- a/bloom.c
+++ b/bloom.c
@@ -66,7 +66,64 @@  int load_bloom_filter_from_graph(struct commit_graph *g,
  * Not considered to be cryptographically secure.
  * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
  */
-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)
+{
+	const uint32_t c1 = 0xcc9e2d51;
+	const uint32_t c2 = 0x1b873593;
+	const uint32_t r1 = 15;
+	const uint32_t r2 = 13;
+	const uint32_t m = 5;
+	const uint32_t n = 0xe6546b64;
+	int i;
+	uint32_t k1 = 0;
+	const char *tail;
+
+	int len4 = len / sizeof(uint32_t);
+
+	uint32_t k;
+	for (i = 0; i < len4; i++) {
+		uint32_t byte1 = (uint32_t)(unsigned char)data[4*i];
+		uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8;
+		uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16;
+		uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24;
+		k = byte1 | byte2 | byte3 | byte4;
+		k *= c1;
+		k = rotate_left(k, r1);
+		k *= c2;
+
+		seed ^= k;
+		seed = rotate_left(seed, r2) * m + n;
+	}
+
+	tail = (data + len4 * sizeof(uint32_t));
+
+	switch (len & (sizeof(uint32_t) - 1)) {
+	case 3:
+		k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16;
+		/*-fallthrough*/
+	case 2:
+		k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8;
+		/*-fallthrough*/
+	case 1:
+		k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0;
+		k1 *= c1;
+		k1 = rotate_left(k1, r1);
+		k1 *= c2;
+		seed ^= k1;
+		break;
+	}
+
+	seed ^= (uint32_t)len;
+	seed ^= (seed >> 16);
+	seed *= 0x85ebca6b;
+	seed ^= (seed >> 13);
+	seed *= 0xc2b2ae35;
+	seed ^= (seed >> 16);
+
+	return seed;
+}
+
+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;
@@ -131,8 +188,14 @@  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);
+	uint32_t hash0, hash1;
+	if (settings->hash_version == 2) {
+		hash0 = murmur3_seeded_v2(seed0, data, len);
+		hash1 = murmur3_seeded_v2(seed1, data, len);
+	} else {
+		hash0 = murmur3_seeded_v1(seed0, data, len);
+		hash1 = murmur3_seeded_v1(seed1, data, len);
+	}
 
 	key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
 	for (i = 0; i < settings->num_hashes; i++)
diff --git a/bloom.h b/bloom.h
index 1e4f612d2c..138d57a86b 100644
--- a/bloom.h
+++ b/bloom.h
@@ -8,9 +8,11 @@  struct commit_graph;
 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.
 	 */
 	uint32_t hash_version;
 
@@ -80,7 +82,7 @@  int load_bloom_filter_from_graph(struct commit_graph *g,
  * Not considered to be cryptographically secure.
  * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
  */
-uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len);
+uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len);
 
 void fill_bloom_key(const char *data,
 		    size_t len,
diff --git a/commit-graph.c b/commit-graph.c
index da99f15fdf..f7322c4fff 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -304,17 +304,26 @@  static int graph_read_oid_lookup(const unsigned char *chunk_start,
 	return 0;
 }
 
+struct graph_read_bloom_data_context {
+	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_context *c = data;
+	struct commit_graph *g = c->g;
 	uint32_t hash_version;
-	g->chunk_bloom_data = chunk_start;
 	hash_version = get_be32(chunk_start);
 
-	if (hash_version != 1)
+	if (*c->commit_graph_changed_paths_version == -1) {
+		*c->commit_graph_changed_paths_version = hash_version;
+	} else if (hash_version != *c->commit_graph_changed_paths_version) {
 		return 0;
+	}
 
+	g->chunk_bloom_data = chunk_start;
 	g->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
 	g->bloom_filter_settings->hash_version = hash_version;
 	g->bloom_filter_settings->num_hashes = get_be32(chunk_start + 4);
@@ -402,10 +411,14 @@  struct commit_graph *parse_commit_graph(struct repo_settings *s,
 	}
 
 	if (s->commit_graph_changed_paths_version) {
+		struct graph_read_bloom_data_context context = {
+			.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, &context);
 	}
 
 	if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
@@ -2376,6 +2389,13 @@  int write_commit_graph(struct object_directory *odb,
 	}
 	if (!commit_graph_compatible(r))
 		return 0;
+	if (r->settings.commit_graph_changed_paths_version < -1
+	    || 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;
+	}
 
 	CALLOC_ARRAY(ctx, 1);
 	ctx->r = r;
@@ -2388,6 +2408,8 @@  int write_commit_graph(struct object_directory *odb,
 	ctx->write_generation_data = (get_configured_generation_version(r) == 2);
 	ctx->num_generation_data_overflows = 0;
 
+	bloom_settings.hash_version = r->settings.commit_graph_changed_paths_version == 2
+		? 2 : 1;
 	bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
 						      bloom_settings.bits_per_entry);
 	bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
@@ -2417,7 +2439,7 @@  int write_commit_graph(struct object_directory *odb,
 		g = ctx->r->objects->commit_graph;
 
 		/* 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;
 		}
diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c
index aabe31d724..3cbc0a5b50 100644
--- a/t/helper/test-bloom.c
+++ b/t/helper/test-bloom.c
@@ -50,6 +50,7 @@  static void get_bloom_filter_for_commit(const struct object_id *commit_oid)
 
 static const char *bloom_usage = "\n"
 "  test-tool bloom get_murmur3 <string>\n"
+"  test-tool bloom get_murmur3_seven_highbit\n"
 "  test-tool bloom generate_filter <string> [<string>...]\n"
 "  test-tool bloom get_filter_for_commit <commit-hex>\n";
 
@@ -64,7 +65,13 @@  int cmd__bloom(int argc, const char **argv)
 		uint32_t hashed;
 		if (argc < 3)
 			usage(bloom_usage);
-		hashed = murmur3_seeded(0, argv[2], strlen(argv[2]));
+		hashed = murmur3_seeded_v2(0, argv[2], strlen(argv[2]));
+		printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
+	}
+
+	if (!strcmp(argv[1], "get_murmur3_seven_highbit")) {
+		uint32_t hashed;
+		hashed = murmur3_seeded_v2(0, "\x99\xaa\xbb\xcc\xdd\xee\xff", 7);
 		printf("Murmur3 Hash with seed=0:0x%08x\n", hashed);
 	}
 
diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh
index b567383eb8..c8d84ab606 100755
--- a/t/t0095-bloom.sh
+++ b/t/t0095-bloom.sh
@@ -29,6 +29,14 @@  test_expect_success 'compute unseeded murmur3 hash for test string 2' '
 	test_cmp expect actual
 '
 
+test_expect_success 'compute unseeded murmur3 hash for test string 3' '
+	cat >expect <<-\EOF &&
+	Murmur3 Hash with seed=0:0xa183ccfd
+	EOF
+	test-tool bloom get_murmur3_seven_highbit >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'compute bloom key for empty string' '
 	cat >expect <<-\EOF &&
 	Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 2d4a3fefee..775e59d864 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -447,4 +447,100 @@  test_expect_success 'version 1 changed-path used when version 1 requested' '
 	)
 '
 
+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"
+	)
+'
+
+test_expect_success 'version 1 changed-path used when autodetect requested' '
+	(
+		cd highbit1 &&
+		git config --add commitgraph.changedPathsVersion -1 &&
+		test_bloom_filters_used "-- $CENT"
+	)
+'
+
+test_expect_success 'when writing another commit graph, preserve existing version 1 of changed-path' '
+	test_commit -C highbit1 c1double "$CENT$CENT" &&
+	git -C highbit1 commit-graph write --reachable --changed-paths &&
+	(
+		cd highbit1 &&
+		git config --add commitgraph.changedPathsVersion -1 &&
+		echo "options: bloom(1,10,7) read_generation_data" >expect &&
+		test-tool read-graph >full &&
+		grep options full >actual &&
+		test_cmp expect actual
+	)
+'
+
+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 &&
+		echo "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"
+	)
+'
+
+test_expect_success 'version 2 changed-path used when autodetect requested' '
+	(
+		cd highbit2 &&
+		git config --add commitgraph.changedPathsVersion -1 &&
+		test_bloom_filters_used "-- $CENT"
+	)
+'
+
+test_expect_success 'when writing another commit graph, preserve existing version 2 of changed-path' '
+	test_commit -C highbit2 c2double "$CENT$CENT" &&
+	git -C highbit2 commit-graph write --reachable --changed-paths &&
+	(
+		cd highbit2 &&
+		git config --add commitgraph.changedPathsVersion -1 &&
+		echo "options: bloom(2,10,7) read_generation_data" >expect &&
+		test-tool read-graph >full &&
+		grep options full >actual &&
+		test_cmp expect actual
+	)
+'
+
+test_expect_success 'when writing commit graph, do not reuse changed-path of another version' '
+	git init doublewrite &&
+	test_commit -C doublewrite c "$CENT" &&
+	git -C doublewrite config --add commitgraph.changedPathsVersion 1 &&
+	git -C doublewrite commit-graph write --reachable --changed-paths &&
+	git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
+	git -C doublewrite commit-graph write --reachable --changed-paths &&
+	(
+		cd doublewrite &&
+		echo "c01f" >expect &&
+		get_first_changed_path_filter >actual &&
+		test_cmp expect actual
+	)
+'
+
 test_done