bloom: changed-path Bloom filters v2 (& sundries)

Taylor Blau git 6 versions Aug 21, 2023 – Jun 25, 2024 New

Get series with b4

b4 am [email protected]

Versions newest first · linked by author and title

v7 Latest Jun 25, 202416 patches 0 repliesNew
v6 Jan 31, 202416 patches 2 repliesSuperseded
v5 Jan 16, 202417 patches 2 repliesSuperseded

Earlier versions · 3

Version	Posted	Patches	Replies	Status
v4	Oct 18, 2023	17 patches	4 replies	Superseded
v3	Oct 10, 2023	17 patches	11 replies	Superseded
v1	Aug 21, 2023	15 patches	14 replies	Superseded

Patches in v7 No applies recorded yet

#	Subject and files	Size	Replies
1/16	t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()``t/t4216-log-bloom.sh`	+13 -1	0 replies
2/16	revision.c: consult Bloom filters for root commits`revision.c` `t/t4216-log-bloom.sh`	+28 -6	0 replies
3/16	commit-graph: ensure Bloom filters are read with consistent settings`commit-graph.c` `t/t4216-log-bloom.sh`	+92 -1	0 replies
4/16	gitformat-commit-graph: describe version 2 of BDAT`Documentation/gitformat-commit-graph.txt`	+6 -3	0 replies
5/16	t/helper/test-read-graph.c: extract `dump_graph_info()``t/helper/test-read-graph.c`	+18 ~~-13~~	0 replies
6/16	bloom.h: make `load_bloom_filter_from_graph()` public`bloom.c` `bloom.h`	+8 -3	0 replies
7/16	t/helper/test-read-graph: implement `bloom-filters` mode`t/helper/test-read-graph.c`	+39 -5	0 replies
8/16	t4216: test changed path filters with high bit paths`t/t4216-log-bloom.sh`	+51 -0	0 replies
9/16	repo-settings: introduce commitgraph.changedPathsVersion`Documentation/config/commitgraph.txt` `commit-graph.c` `oss-fuzz/fuzz-commit-graph.c` +2 more	+33 -8	0 replies
10/16	bloom: annotate filters with hash version`bloom.c` `bloom.h`	+9 -3	0 replies
11/16	bloom: prepare to discard incompatible Bloom filters`bloom.c` `bloom.h`	+37 -3	0 replies
12/16	commit-graph: unconditionally load Bloom filters`commit-graph.c`	+10 -4	0 replies
13/16	commit-graph: new Bloom filter version that fixes murmur3`Documentation/config/commitgraph.txt` `bloom.c` `bloom.h` +4 more	+252 ~~-15~~	0 replies
14/16	object.h: fix mis-aligned flag bits table`object.h`	+1 -1	0 replies
15/16	commit-graph: reuse existing Bloom filters where possible`bloom.c` `bloom.h` `commit-graph.c` +2 more	+132 -4	0 replies
16/16	bloom: introduce `deinit_bloom_filters()``bloom.c` `bloom.h` `commit-graph.c`	+22 -1	0 replies

Reviews trailers per patch

None of the 16 patches has a Reviewed-by or Acked-by.

Patch	Jonathan Tan	SZEDER Gábor
1/16
2/16	Original-patch-by
3/16		Original-test-by
4/16
5/16
6/16
7/16
8/16
9/16
10/16
11/16
12/16
13/16
14/16
15/16
16/16

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v7 thread

Cover letter [PATCH v7 00/16] bloom: changed-path Bloom filters v2 (& sundries)

(Rebased onto the tip of 'master', which is now 1e1586e4ed (The sixteenth batch, 2024-06-24) at the time of writing).

This series is another minor reroll of the combined efforts of [1] and
[2] to introduce the v2 changed-path Bloom filters, which fixes a bug in our existing implementation of murmur3 paths with non-ASCII characters (when the "char" type is signed).

This version addresses the remaining comments from SZEDER around more thorough testing of merging commit-graph layers with incompatible Bloom filters versions, and ensuring the result is as expected.

Thanks again to Jonathan, Peff, and SZEDER who have helped a great deal in assembling these patches. As usual, a range-diff is included below.

Thanks in advance for your review!

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

Jonathan Tan (1):
gitformat-commit-graph: describe version 2 of BDAT

Taylor Blau (15):
t/t4216-log-bloom.sh: harden test_bloom_filters_not_used() revision.c: consult Bloom filters for root commits
commit-graph: ensure Bloom filters are read with consistent settings 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
t4216: test changed path filters with high bit paths
repo-settings: introduce commitgraph.changedPathsVersion
bloom: annotate filters with hash version
bloom: prepare to discard incompatible Bloom filters
commit-graph: unconditionally load Bloom filters
commit-graph: new Bloom filter version that fixes murmur3 object.h: fix mis-aligned flag bits table
commit-graph: reuse existing Bloom filters where possible
bloom: introduce deinit_bloom_filters()

 Documentation/config/commitgraph.txt     |  29 +-
 Documentation/gitformat-commit-graph.txt |   9 +-
 bloom.c                                  | 208 ++++++++++++++-
 bloom.h                                  |  38 ++-
 commit-graph.c                           |  64 ++++-
 object.h                                 |   3 +-
 oss-fuzz/fuzz-commit-graph.c             |   2 +-
 repo-settings.c                          |   6 +-
 repository.h                             |   2 +-
 revision.c                               |  26 +-
 t/helper/test-bloom.c                    |   9 +-
 t/helper/test-read-graph.c               |  67 ++++-
 t/t0095-bloom.sh                         |   8 +
 t/t4216-log-bloom.sh                     | 325 ++++++++++++++++++++++-
 14 files changed, 738 insertions(+), 58 deletions(-)

Range-diff against v6:

 1:  9df34a2f4f =  1:  ee651fee33 t/t4216-log-bloom.sh: harden `test_bloom_filters_not_used()`
 2:  a6dc377f1b =  2:  5d88ad6c90 revision.c: consult Bloom filters for root commits
 3:  a77ab941bc !  3:  f6cf5bfc4e commit-graph: ensure Bloom filters are read with consistent settings
    @@ t/t4216-log-bloom.sh: test_expect_success 'Bloom generation backfills empty comm
     +test_expect_success 'merge graph layers with incompatible Bloom settings' '
     +	# Ensure that incompatible Bloom filters are ignored when
     +	# merging existing layers.
    -+	git -C $repo commit-graph write --reachable --changed-paths 2>err &&
    ++	>trace2.txt &&
    ++	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
    ++		git -C $repo commit-graph write --reachable --changed-paths 2>err &&
     +	grep "disabling Bloom filters for commit-graph layer .$layer." err &&
    ++	grep "{\"hash_version\":1,\"num_hashes\":7,\"bits_per_entry\":10,\"max_changed_paths\":512" trace2.txt &&
     +
     +	test_path_is_file $repo/$graph &&
     +	test_dir_is_empty $repo/$graphdir &&
 4:  56a9fdaff0 =  4:  0041600f31 gitformat-commit-graph: describe version 2 of BDAT
 5:  7484a82f7f =  5:  6e7f317551 t/helper/test-read-graph.c: extract `dump_graph_info()`
 6:  48343f93a2 =  6:  ae74fbad3e bloom.h: make `load_bloom_filter_from_graph()` public
 7:  286fd7dcdb =  7:  0dfd1a361e t/helper/test-read-graph: implement `bloom-filters` mode
 8:  7de7b89da0 =  8:  fbcaa686b1 t4216: test changed path filters with high bit paths
 9:  b13c9b8ff9 !  9:  60c063ca4a repo-settings: introduce commitgraph.changedPathsVersion
    @@ commit-graph.c: static void validate_mixed_bloom_settings(struct commit_graph *g
     
      ## oss-fuzz/fuzz-commit-graph.c ##
     @@ oss-fuzz/fuzz-commit-graph.c: int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size)
    - 	 * possible.
      	 */
    + 	repo_set_hash_algo(the_repository, GIT_HASH_SHA1);
      	the_repository->settings.commit_graph_generation_version = 2;
     -	the_repository->settings.commit_graph_read_changed_paths = 1;
     +	the_repository->settings.commit_graph_changed_paths_version = 1;
10:  09c44c51a5 = 10:  ce3a15a517 bloom: annotate filters with hash version
11:  d4995ef600 = 11:  99ab9cf448 bloom: prepare to discard incompatible Bloom filters
12:  c8e9bb7c88 = 12:  99e66d1dba commit-graph: unconditionally load Bloom filters
13:  d2f11c082d ! 13:  2e945c3d2e commit-graph: new Bloom filter version that fixes murmur3
    @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
     +	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"),
    ++			  "'commitGraph.changedPathsVersion' (%d) is not supported"),
     +			r->settings.commit_graph_changed_paths_version);
     +		return 0;
     +	}
    @@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible
      	test_must_be_empty err
      '
      
    ++# chosen to be the same under all Unicode normalization forms
    ++CENT=$(printf "\302\242")
    ++
     +test_expect_success 'ensure Bloom filter with incompatible versions are ignored' '
     +	rm "$repo/$graph" &&
     +
    @@ t/t4216-log-bloom.sh: test_expect_success 'merge graph layers with incompatible
     +	cat >expect.err <<-EOF &&
     +	warning: disabling Bloom filters for commit-graph layer $SQ$layer$SQ due to incompatible settings
     +	EOF
    -+	test_cmp expect.err err
    ++	test_cmp expect.err err &&
    ++
    ++	# Merge the two layers with incompatible bloom filter versions,
    ++	# ensuring that the v2 filters are used.
    ++	>trace2.txt &&
    ++	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
    ++		git -C $repo -c commitGraph.changedPathsVersion=2 commit-graph write --reachable --changed-paths 2>err &&
    ++	grep "disabling Bloom filters for commit-graph layer .$layer." err &&
    ++	grep "{\"hash_version\":2,\"num_hashes\":7,\"bits_per_entry\":10,\"max_changed_paths\":512" trace2.txt
     +'
     +
      get_first_changed_path_filter () {
      	test-tool read-graph bloom-filters >filters.dat &&
      	head -n 1 filters.dat
    + }
    + 
    +-# chosen to be the same under all Unicode normalization forms
    +-CENT=$(printf "\302\242")
    +-
    + test_expect_success 'set up repo with high bit path, version 1 changed-path' '
    + 	git init highbit1 &&
    + 	test_commit -C highbit1 c1 "$CENT" &&
     @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when version 1 requested' '
      	)
      '
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +test_expect_success 'version 1 changed-path not used when version 2 requested' '
     +	(
     +		cd highbit1 &&
    -+		git config --add commitgraph.changedPathsVersion 2 &&
    ++		git config --add commitGraph.changedPathsVersion 2 &&
     +		test_bloom_filters_not_used "-- another$CENT"
     +	)
     +'
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +test_expect_success 'version 1 changed-path used when autodetect requested' '
     +	(
     +		cd highbit1 &&
    -+		git config --add commitgraph.changedPathsVersion -1 &&
    ++		git config --add commitGraph.changedPathsVersion -1 &&
     +		test_bloom_filters_used "-- another$CENT"
     +	)
     +'
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +	git -C highbit1 commit-graph write --reachable --changed-paths &&
     +	(
     +		cd highbit1 &&
    -+		git config --add commitgraph.changedPathsVersion -1 &&
    ++		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 &&
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +
     +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 &&
    ++	git -C highbit2 config --add commitGraph.changedPathsVersion 2 &&
     +	test_commit -C highbit2 c2 "$CENT" &&
     +	git -C highbit2 commit-graph write --reachable --changed-paths
     +'
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +test_expect_success 'version 2 changed-path not used when version 1 requested' '
     +	(
     +		cd highbit2 &&
    -+		git config --add commitgraph.changedPathsVersion 1 &&
    ++		git config --add commitGraph.changedPathsVersion 1 &&
     +		test_bloom_filters_not_used "-- another$CENT"
     +	)
     +'
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +test_expect_success 'version 2 changed-path used when autodetect requested' '
     +	(
     +		cd highbit2 &&
    -+		git config --add commitgraph.changedPathsVersion -1 &&
    ++		git config --add commitGraph.changedPathsVersion -1 &&
     +		test_bloom_filters_used "-- another$CENT"
     +	)
     +'
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +	git -C highbit2 commit-graph write --reachable --changed-paths &&
     +	(
     +		cd highbit2 &&
    -+		git config --add commitgraph.changedPathsVersion -1 &&
    ++		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 &&
    @@ t/t4216-log-bloom.sh: test_expect_success 'version 1 changed-path used when vers
     +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 config --add commitGraph.changedPathsVersion 1 &&
     +	git -C doublewrite commit-graph write --reachable --changed-paths &&
     +	for v in -2 3
     +	do
    -+		git -C doublewrite config --add commitgraph.changedPathsVersion $v &&
    ++		git -C doublewrite config --add commitGraph.changedPathsVersion $v &&
     +		git -C doublewrite commit-graph write --reachable --changed-paths 2>err &&
     +		cat >expect <<-EOF &&
    -+		warning: attempting to write a commit-graph, but ${SQ}commitgraph.changedPathsVersion${SQ} ($v) is not supported
    ++		warning: attempting to write a commit-graph, but ${SQ}commitGraph.changedPathsVersion${SQ} ($v) is not supported
     +		EOF
     +		test_cmp expect err || return 1
     +	done &&
    -+	git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
    ++	git -C doublewrite config --add commitGraph.changedPathsVersion 2 &&
     +	git -C doublewrite commit-graph write --reachable --changed-paths &&
     +	(
     +		cd doublewrite &&
14:  9f54a376fb = 14:  242f023135 object.h: fix mis-aligned flag bits table
15:  67991dea7c ! 15:  1b80023e57 commit-graph: reuse existing Bloom filters where possible
    @@ bloom.c: static void init_truncated_large_filter(struct bloom_filter *filter,
     +		struct tree_desc desc;
     +		struct name_entry entry;
     +
    -+		init_tree_desc(&desc, t->buffer, t->size);
    ++		init_tree_desc(&desc, &t->object.oid, t->buffer, t->size);
     +		while (tree_entry(&desc, &entry)) {
     +			size_t i;
     +			for (i = 0; i < entry.pathlen; i++) {
    @@ t/t4216-log-bloom.sh: test_expect_success 'when writing another commit graph, pr
      	git init doublewrite &&
      	test_commit -C doublewrite c "$CENT" &&
     +
    - 	git -C doublewrite config --add commitgraph.changedPathsVersion 1 &&
    + 	git -C doublewrite config --add commitGraph.changedPathsVersion 1 &&
    ++	>trace2.txt &&
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
     +		git -C doublewrite commit-graph write --reachable --changed-paths &&
     +	test_filter_computed 1 trace2.txt &&
    @@ t/t4216-log-bloom.sh: test_expect_success 'when writing commit graph, do not reu
      		test_cmp expect err || return 1
      	done &&
     +
    - 	git -C doublewrite config --add commitgraph.changedPathsVersion 2 &&
    + 	git -C doublewrite config --add commitGraph.changedPathsVersion 2 &&
     -	git -C doublewrite commit-graph write --reachable --changed-paths &&
    ++	>trace2.txt &&
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
     +		git -C doublewrite commit-graph write --reachable --changed-paths &&
     +	test_filter_computed 1 trace2.txt &&
    @@ t/t4216-log-bloom.sh: test_expect_success 'when writing commit graph, do not reu
     +
     +	test_commit -C upgrade base no-high-bits &&
     +
    -+	git -C upgrade config --add commitgraph.changedPathsVersion 1 &&
    ++	git -C upgrade config --add commitGraph.changedPathsVersion 1 &&
    ++	>trace2.txt &&
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
     +		git -C upgrade commit-graph write --reachable --changed-paths &&
     +	test_filter_computed 1 trace2.txt &&
     +	test_filter_upgraded 0 trace2.txt &&
     +
    -+	git -C upgrade config --add commitgraph.changedPathsVersion 2 &&
    ++	git -C upgrade config --add commitGraph.changedPathsVersion 2 &&
    ++	>trace2.txt &&
     +	GIT_TRACE2_EVENT="$(pwd)/trace2.txt" \
     +		git -C upgrade commit-graph write --reachable --changed-paths &&
     +	test_filter_computed 0 trace2.txt &&

16: 12058a074d = 16: db9991f339 bloom: introduce deinit_bloom_filters()

base-commit: 1e1586e4ed626bde864339c10570bc0e73f0ab97

Signature · 1 line

2.45.2.664.g446e6a2b1f

Read the cover letter in its thread