Re: [PATCH v3 10/17] commit-graph: new filter ver. that fixes murmur3

[Patrick Steinhardt <ps@pks.im>]

[-- Attachment #1: Type: text/plain, Size: 17868 bytes --]

On Tue, Oct 10, 2023 at 04:33:49PM -0400, Taylor Blau wrote:
> From: Jonathan Tan <jonathantanmy@google.com>
> 
> 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 <jonathantanmy@google.com>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
>  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                 | 105 +++++++++++++++++++++++++++
>  7 files changed, 223 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)
> +{
> +	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 ea677c87fb..db623afd09 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -314,17 +314,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;
> +	}

In case we have `c->commit_graph_changed_paths_version == -1` we lose
the check that the hash version is something that we know and support,
don't we? And while we do start to handle `-1` in the writing path, I
think we don't in the reading path unless I missed something.

> +	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);
> @@ -412,10 +421,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) {
> @@ -2441,6 +2454,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;
> @@ -2453,6 +2473,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",
> @@ -2482,7 +2504,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 da67c40134..8f8b5d4966 100755
> --- a/t/t4216-log-bloom.sh
> +++ b/t/t4216-log-bloom.sh
> @@ -536,4 +536,109 @@ 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 "-- another$CENT"
> +	)
> +'
> +
> +test_expect_success 'version 1 changed-path used when autodetect requested' '
> +	(
> +		cd highbit1 &&
> +		git config --add commitgraph.changedPathsVersion -1 &&
> +		test_bloom_filters_used "-- another$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 'setup make another commit' '
> +	# "git log" does not use Bloom filters for root commits - see how, in
> +	# revision.c, rev_compare_tree() (the only code path that eventually calls
> +	# get_bloom_filter()) is only called by try_to_simplify_commit() when the commit
> +	# has one parent. Therefore, make another commit so that we perform the tests on
> +	# a non-root commit.
> +	test_commit -C highbit2 anotherc2 "another$CENT"
> +'
> +
> +test_expect_success 'version 2 changed-path used when version 2 requested' '
> +	(
> +		cd highbit2 &&
> +		test_bloom_filters_used "-- another$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 "-- another$CENT"
> +	)
> +'
> +
> +test_expect_success 'version 2 changed-path used when autodetect requested' '
> +	(
> +		cd highbit2 &&
> +		git config --add commitgraph.changedPathsVersion -1 &&
> +		test_bloom_filters_used "-- another$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
> +	)
> +'
> +

With the supposedly missing check in mind, should we also add tests for
currently unknown versions like 3 or -2?

Patrick

>  test_done
> -- 
> 2.42.0.342.g8bb3a896ee
> 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]