Subject: [PATCH v7 0/7] Changed path filter hash fix and version bump

From: Jonathan Tan <[email-masked]>
Date: Tue, 1 Aug 2023 11:41:35 -0700

I've fixed the bug that Taylor described. It was an issue where the
presence of Bloom filters can be indicated both by the presence of the
chunk and the presence of a bloom_filter_settings, and I've fixed it by
avoiding setting the chunk_bloom_data if we're not using Bloom filters
due to an incompatible version. In the future, we might want to refactor
the code so that there is only one way to indicate whether the Bloom
filters are present.

I've also added sign-offs and changed the indentation of the tests, as
remarked by Taylor [1] [2].

[1] https://lore.kernel.org/git/[email-masked]/
[2] https://lore.kernel.org/git/[email-masked]/

Taylor also suggested copying forward Bloom filters whenever possible
in this patch set [3], but also that we could work on this outside this
series [4]. I did not implement this in this series.

[3] https://lore.kernel.org/git/[email-masked]/
[4] https://lore.kernel.org/git/[email-masked]/

Jonathan Tan (4):
  gitformat-commit-graph: describe version 2 of BDAT
  t4216: test changed path filters with high bit paths
  repo-settings: introduce commitgraph.changedPathsVersion
  commit-graph: new filter ver. that fixes murmur3

Taylor Blau (3):
  t/helper/test-read-graph.c: extract `dump_graph_info()`
  bloom.h: make `load_bloom_filter_from_graph()` public
  t/helper/test-read-graph: implement `bloom-filters` mode

 Documentation/config/commitgraph.txt     |  26 ++++-
 Documentation/gitformat-commit-graph.txt |   9 +-
 bloom.c                                  |  75 +++++++++++-
 bloom.h                                  |  13 ++-
 commit-graph.c                           |  35 ++++--
 oss-fuzz/fuzz-commit-graph.c             |   2 +-
 repo-settings.c                          |   6 +-
 repository.h                             |   2 +-
 t/helper/test-bloom.c                    |   9 +-
 t/helper/test-read-graph.c               |  67 ++++++++---
 t/t0095-bloom.sh                         |   8 ++
 t/t4216-log-bloom.sh                     | 139 +++++++++++++++++++++++
 12 files changed, 351 insertions(+), 40 deletions(-)

Range-diff against v6:
1:  3ce6090a4d = 1:  3ce6090a4d gitformat-commit-graph: describe version 2 of BDAT
2:  1955734d1f ! 2:  fc6346c039 t/helper/test-read-graph.c: extract `dump_graph_info()`
    @@ Commit message
         main routine into a separate function.
     
         Signed-off-by: Taylor Blau <[email-masked]>
    +    Signed-off-by: Jonathan Tan <[email-masked]>
     
      ## t/helper/test-read-graph.c ##
     @@
3:  4cf7c2f634 ! 3:  f144dc4b15 bloom.h: make `load_bloom_filter_from_graph()` public
    @@ Commit message
         for manual inspection (to be used during tests).
     
         Signed-off-by: Taylor Blau <[email-masked]>
    +    Signed-off-by: Jonathan Tan <[email-masked]>
     
      ## bloom.c ##
     @@ bloom.c: static inline unsigned char get_bitmask(uint32_t pos)
4:  47b55758e6 ! 4:  2ade832a23 t/helper/test-read-graph: implement `bloom-filters` mode
    @@ Commit message
         hexadecimal contents of the Bloom filter(s) contained in a commit-graph.
     
         Signed-off-by: Taylor Blau <[email-masked]>
    +    Signed-off-by: Jonathan Tan <[email-masked]>
     
      ## t/helper/test-read-graph.c ##
     @@ t/helper/test-read-graph.c: static void dump_graph_info(struct commit_graph *graph)
5:  5276e6a90e ! 5:  74863c11e5 t4216: test changed path filters with high bit paths
    @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm
     +'
     +
     +test_expect_success 'setup check value of version 1 changed-path' '
    -+	(cd highbit1 &&
    ++	(
    ++		cd highbit1 &&
     +		echo "52a9" >expect &&
     +		get_first_changed_path_filter >actual &&
    -+		test_cmp expect actual)
    ++		test_cmp expect actual
    ++	)
     +'
     +
     +# expect will not match actual if char is unsigned by default. Write the test
    @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm
     +'
     +
     +test_expect_success 'version 1 changed-path used when version 1 requested' '
    -+	(cd highbit1 &&
    -+		test_bloom_filters_used "-- $CENT")
    ++	(
    ++		cd highbit1 &&
    ++		test_bloom_filters_used "-- $CENT"
    ++	)
     +'
     +
      test_done
6:  dc3f6d2d4f = 6:  60f4faeff9 repo-settings: introduce commitgraph.changedPathsVersion
7:  6e2d797406 ! 7:  68258cfd04 commit-graph: new filter ver. that fixes murmur3
    @@ commit-graph.c: static int graph_read_oid_lookup(const unsigned char *chunk_star
     +	struct graph_read_bloom_data_context *c = data;
     +	struct commit_graph *g = c->g;
      	uint32_t hash_version;
    - 	g->chunk_bloom_data = chunk_start;
    +-	g->chunk_bloom_data = chunk_start;
      	hash_version = get_be32(chunk_start);
      
     -	if (hash_version != 1)
    @@ commit-graph.c: static int graph_read_oid_lookup(const unsigned char *chunk_star
     + 		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);
     @@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repo_settings *s,
      	}
      
    @@ t/t0095-bloom.sh: test_expect_success 'compute unseeded murmur3 hash for test st
      	Hashes:0x5615800c|0x5b966560|0x61174ab4|0x66983008|0x6c19155c|0x7199fab0|0x771ae004|
     
      ## t/t4216-log-bloom.sh ##
    -@@ t/t4216-log-bloom.sh: test_expect_success 'set up repo with high bit path, version 1 changed-path' '
    - 	git -C highbit1 commit-graph write --reachable --changed-paths
    - '
    - 
    --test_expect_success 'setup check value of version 1 changed-path' '
    -+test_expect_success 'check value of version 1 changed-path' '
    - 	(cd highbit1 &&
    - 		echo "52a9" >expect &&
    - 		get_first_changed_path_filter >actual &&
     @@ t/t4216-log-bloom.sh: 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 &&
    ++	(
    ++		cd highbit1 &&
     +		git config --add commitgraph.changedPathsVersion 2 &&
    -+		test_bloom_filters_not_used "-- $CENT")
    ++		test_bloom_filters_not_used "-- $CENT"
    ++	)
     +'
     +
     +test_expect_success 'version 1 changed-path used when autodetect requested' '
    -+	(cd highbit1 &&
    ++	(
    ++		cd highbit1 &&
     +		git config --add commitgraph.changedPathsVersion -1 &&
    -+		test_bloom_filters_used "-- $CENT")
    ++		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 &&
    ++	(
    ++		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_cmp expect actual
    ++	)
     +'
     +
     +test_expect_success 'set up repo with high bit path, version 2 changed-path' '
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +'
     +
     +test_expect_success 'check value of version 2 changed-path' '
    -+	(cd highbit2 &&
    ++	(
    ++		cd highbit2 &&
     +		echo "c01f" >expect &&
     +		get_first_changed_path_filter >actual &&
    -+		test_cmp expect actual)
    ++		test_cmp expect actual
    ++	)
     +'
     +
     +test_expect_success 'version 2 changed-path used when version 2 requested' '
    -+	(cd highbit2 &&
    -+		test_bloom_filters_used "-- $CENT")
    ++	(
    ++		cd highbit2 &&
    ++		test_bloom_filters_used "-- $CENT"
    ++	)
     +'
     +
     +test_expect_success 'version 2 changed-path not used when version 1 requested' '
    -+	(cd highbit2 &&
    ++	(
    ++		cd highbit2 &&
     +		git config --add commitgraph.changedPathsVersion 1 &&
    -+		test_bloom_filters_not_used "-- $CENT")
    ++		test_bloom_filters_not_used "-- $CENT"
    ++	)
     +'
     +
     +test_expect_success 'version 2 changed-path used when autodetect requested' '
    -+	(cd highbit2 &&
    ++	(
    ++		cd highbit2 &&
     +		git config --add commitgraph.changedPathsVersion -1 &&
    -+		test_bloom_filters_used "-- $CENT")
    ++		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 &&
    ++	(
    ++		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_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
-- 
2.41.0.585.gd2178a4bd4-goog