git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 01/13] commit-graph: introduce 'get_bloom_filter_settings()'

From
Taylor Blau <me@ttaylorr.com>
Date
Sep 16, 2020, 18:06 UTC
Message-ID
<db305fe3d698f297f1d3359516f5e5d18627adbe.1600279373.git.me@ttaylorr.com>
In-Reply-To
<cover.1600279373.git.me@ttaylorr.com>

Many places in the code often need a pointer to the commit-graph's 'struct bloom_filter_settings', in which case they often take the value from the top-most commit-graph.

In the non-split case, this works as expected. In the split case, however, things get a little tricky. Not all layers in a chain of incremental commit-graphs are required to themselves have Bloom data, and so whether or not some part of the code uses Bloom filters depends entirely on whether or not the top-most level of the commit-graph chain has Bloom filters.

This has been the behavior since Bloom filters were introduced, and has been codified into the tests since a759bfa9ee (t4216: add end to end tests for git log with Bloom filters, 2020-04-06). In fact, t4216.130 requires that Bloom filters are not used in exactly the case described earlier.

There is no reason that this needs to be the case, since it is perfectly valid for commits in an earlier layer to have Bloom filters when commits in a newer layer do not.

Since Bloom settings are guaranteed in practice to be the same for any layer in a chain that has Bloom data, it is sufficient to traverse the '->base_graph' pointer until either (1) a non-null 'struct bloom_filter_settings *' is found, or (2) until we are at the root of the commit-graph chain.

Introduce a 'get_bloom_filter_settings()' function that does just this, and use it instead of purely dereferencing the top-most graph's '->bloom_filter_settings' pointer.

While we're at it, add an additional test in t5324 to guard against code in the commit-graph writing machinery that doesn't correctly handle a NULL 'struct bloom_filter *'.

Co-authored-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
 blame.c                       |  6 ++++--
 bloom.c                       |  6 +++---
 commit-graph.c                | 11 +++++++++++
 commit-graph.h                |  2 ++
 revision.c                    |  5 +----
 t/t4216-log-bloom.sh          |  9 ++++++---
 t/t5324-split-commit-graph.sh | 13 +++++++++++++
 7 files changed, 40 insertions(+), 12 deletions(-)
diff --git a/blame.c b/blame.c
index 1be1cd82a2..903e23af23 100644
--- a/blame.c
+++ b/blame.c
@@ -2892,16 +2892,18 @@ void setup_blame_bloom_data(struct blame_scoreboard *sb,
 			    const char *path)
 {
 	struct blame_bloom_data *bd;
+	struct bloom_filter_settings *bs;
 
 	if (!sb->repo->objects->commit_graph)
 		return;
 
-	if (!sb->repo->objects->commit_graph->bloom_filter_settings)
+	bs = get_bloom_filter_settings(sb->repo);
+	if (!bs)
 		return;
 
 	bd = xmalloc(sizeof(struct blame_bloom_data));
 
-	bd->settings = sb->repo->objects->commit_graph->bloom_filter_settings;
+	bd->settings = bs;
 
 	bd->alloc = 4;
 	bd->nr = 0;
diff --git a/bloom.c b/bloom.c
index 1a573226e7..cd9380ac62 100644
--- a/bloom.c
+++ b/bloom.c
@@ -38,7 +38,7 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,
 	while (graph_pos < g->num_commits_in_base)
 		g = g->base_graph;
 
-	/* The commit graph commit 'c' lives in doesn't carry bloom filters. */
+	/* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
 	if (!g->chunk_bloom_indexes)
 		return 0;
 
@@ -195,8 +195,8 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 	if (!filter->data) {
 		load_commit_graph_info(r, c);
 		if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH &&
-			r->objects->commit_graph->chunk_bloom_indexes)
-			load_bloom_filter_from_graph(r->objects->commit_graph, filter, c);
+			load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
+				return filter;
 	}
 
 	if (filter->data)
diff --git a/commit-graph.c b/commit-graph.c
index 0ed003e218..6a36ed0b06 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -667,6 +667,17 @@ int generation_numbers_enabled(struct repository *r)
 	return !!first_generation;
 }
 
+struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)
+{
+	struct commit_graph *g = r->objects->commit_graph;
+	while (g) {
+		if (g->bloom_filter_settings)
+			return g->bloom_filter_settings;
+		g = g->base_graph;
+	}
+	return NULL;
+}
+
 static void close_commit_graph_one(struct commit_graph *g)
 {
 	if (!g)
diff --git a/commit-graph.h b/commit-graph.h
index 09a97030dc..0677dd1031 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -87,6 +87,8 @@ struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size);
  */
 int generation_numbers_enabled(struct repository *r);
 
+struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r);
+
 enum commit_graph_write_flags {
 	COMMIT_GRAPH_WRITE_APPEND     = (1 << 0),
 	COMMIT_GRAPH_WRITE_PROGRESS   = (1 << 1),
diff --git a/revision.c b/revision.c
index 1239023f93..6aeb764821 100644
--- a/revision.c
+++ b/revision.c
@@ -681,10 +681,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)
 
 	repo_parse_commit(revs->repo, revs->commits->item);
 
-	if (!revs->repo->objects->commit_graph)
-		return;
-
-	revs->bloom_filter_settings = revs->repo->objects->commit_graph->bloom_filter_settings;
+	revs->bloom_filter_settings = get_bloom_filter_settings(revs->repo);
 	if (!revs->bloom_filter_settings)
 		return;
 
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index 4bb9e9dbe2..715912ad0f 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -65,7 +65,7 @@ setup () {
 
 test_bloom_filters_used () {
 	log_args=$1
-	bloom_trace_prefix="statistics:{\"filter_not_present\":0,\"maybe\""
+	bloom_trace_prefix="statistics:{\"filter_not_present\":${2:-0},\"maybe\""
 	setup "$log_args" &&
 	grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
 	test_cmp log_wo_bloom log_w_bloom &&
@@ -139,8 +139,11 @@ test_expect_success 'setup - add commit-graph to the chain without Bloom filters
 	test_line_count = 2 .git/objects/info/commit-graphs/commit-graph-chain
 '
 
-test_expect_success 'Do not use Bloom filters if the latest graph does not have Bloom filters.' '
-	test_bloom_filters_not_used "-- A/B"
+test_expect_success 'use Bloom filters even if the latest graph does not have Bloom filters' '
+	# Ensure that the number of empty filters is equal to the number of
+	# filters in the latest graph layer to prove that they are loaded (and
+	# ignored).
+	test_bloom_filters_used "-- A/B" 3
 '
 
 test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '
diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
index 18216463c7..c334ee9155 100755
--- a/t/t5324-split-commit-graph.sh
+++ b/t/t5324-split-commit-graph.sh
@@ -427,4 +427,17 @@ done <<\EOF
 0600 -r--------
 EOF
 
+test_expect_success '--split=replace with partial Bloom data' '
+	rm -rf $graphdir $infodir/commit-graph &&
+	git reset --hard commits/3 &&
+	git rev-list -1 HEAD~2 >a &&
+	git rev-list -1 HEAD~1 >b &&
+	git commit-graph write --split=no-merge --stdin-commits --changed-paths <a &&
+	git commit-graph write --split=no-merge --stdin-commits <b &&
+	git commit-graph write --split=replace --stdin-commits --changed-paths <c &&
+	ls $graphdir/graph-*.graph >graph-files &&
+	test_line_count = 1 graph-files &&
+	verify_chain_files_exist $graphdir
+'
+
 test_done

-- 
2.28.0.510.g86fdc5f89a
Previous: Taylor BlauNext: Taylor Blau
Message 35 of 75 in “more miscellaneous Bloom filter improvements, redux”
  1. 00/12 more miscellaneous Bloom filter improvements, reduxTaylor Blau, Sep 9, 2020
  2. 03/12 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Sep 9, 2020
  3. 11/12 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Sep 9, 2020
  4. 12/12 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Sep 9, 2020
  5. Jeff KingSep 11, 2020
  6. Taylor BlauSep 11, 2020
  7. Taylor BlauSep 11, 2020
  8. Taylor BlauSep 14, 2020
  9. Derrick StoleeSep 14, 2020
  10. Taylor BlauSep 14, 2020
  11. Derrick StoleeSep 15, 2020
  12. Taylor BlauSep 15, 2020
  13. Junio C HamanoSep 15, 2020
  14. Taylor BlauSep 15, 2020
  15. Jeff KingSep 11, 2020
  16. Junio C HamanoSep 11, 2020
  17. 04/12 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Sep 9, 2020
  18. 05/12 commit-graph: respect 'commitGraph.readChangedPaths'Taylor Blau, Sep 9, 2020
  19. 08/12 bloom: use provided 'struct bloom_filter_settings'Taylor Blau, Sep 9, 2020
  20. 06/12 commit-graph.c: store maximum changed pathsTaylor Blau, Sep 9, 2020
  21. 09/12 bloom/diff: properly short-circuit on max_changesTaylor Blau, Sep 9, 2020
  22. 10/12 bloom: encode out-of-bounds filters as non-emptyTaylor Blau, Sep 9, 2020
  23. Taylor BlauSep 10, 2020
  24. Taylor BlauSep 10, 2020
  25. Derrick StoleeSep 11, 2020
  26. 07/12 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Sep 9, 2020
  27. 02/12 t4216: use an '&&'-chainTaylor Blau, Sep 9, 2020
  28. 01/12 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Sep 9, 2020
  29. 00/13 more miscellaneous Bloom filter improvements, reduxTaylor Blau, Sep 16, 2020
  30. 04/13 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Sep 16, 2020
  31. 03/13 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Sep 16, 2020
  32. 05/13 commit-graph: respect 'commitGraph.readChangedPaths'Taylor Blau, Sep 16, 2020
  33. 06/13 commit-graph.c: store maximum changed pathsTaylor Blau, Sep 16, 2020
  34. 02/13 t4216: use an '&&'-chainTaylor Blau, Sep 16, 2020
  35. 01/13 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Sep 16, 2020
  36. 07/13 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Sep 16, 2020
  37. 08/13 bloom: use provided 'struct bloom_filter_settings'Taylor Blau, Sep 16, 2020
  38. 10/13 bloom: encode out-of-bounds filters as non-emptyTaylor Blau, Sep 16, 2020
  39. SZEDER GáborSep 17, 2020
  40. Taylor BlauSep 17, 2020
  41. Junio C HamanoSep 18, 2020
  42. Taylor BlauSep 18, 2020
  43. 11/13 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Sep 16, 2020
  44. 12/13 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Sep 16, 2020
  45. SZEDER GáborSep 18, 2020
  46. Taylor BlauSep 18, 2020
  47. 09/13 bloom/diff: properly short-circuit on max_changesTaylor Blau, Sep 16, 2020
  48. 13/13 commit-graph: introduce 'commitGraph.maxNewFilters'Taylor Blau, Sep 16, 2020
  49. Derrick StoleeSep 16, 2020
  50. Junio C HamanoSep 16, 2020
  51. Taylor BlauSep 17, 2020
  52. Junio C HamanoSep 17, 2020
  53. Taylor BlauSep 17, 2020
  54. Taylor BlauSep 17, 2020
  55. Derrick StoleeSep 17, 2020
  56. 00/13 more miscellaneous Bloom filter improvements, reduxTaylor Blau, Sep 18, 2020
  57. 01/13 commit-graph: introduce 'get_bloom_filter_settings()'Taylor Blau, Sep 18, 2020
  58. 03/13 commit-graph: pass a 'struct repository *' in more placesTaylor Blau, Sep 18, 2020
  59. 02/13 t4216: use an '&&'-chainTaylor Blau, Sep 18, 2020
  60. 05/13 commit-graph: respect 'commitGraph.readChangedPaths'Taylor Blau, Sep 18, 2020
  61. 04/13 t/helper/test-read-graph.c: prepare repo settingsTaylor Blau, Sep 18, 2020
  62. 08/13 bloom: use provided 'struct bloom_filter_settings'Taylor Blau, Sep 18, 2020
  63. SZEDER GáborSep 18, 2020
  64. Taylor BlauSep 18, 2020
  65. 07/13 bloom: split 'get_bloom_filter()' in twoTaylor Blau, Sep 18, 2020
  66. 06/13 commit-graph.c: store maximum changed pathsTaylor Blau, Sep 18, 2020
  67. 10/13 bloom: encode out-of-bounds filters as non-emptyTaylor Blau, Sep 18, 2020
  68. 11/13 commit-graph: rename 'split_commit_graph_opts'Taylor Blau, Sep 18, 2020
  69. 13/13 commit-graph: introduce 'commitGraph.maxNewFilters'Taylor Blau, Sep 18, 2020
  70. Taylor BlauSep 18, 2020
  71. Junio C HamanoSep 18, 2020
  72. 12/13 builtin/commit-graph.c: introduce '--max-new-filters=<n>'Taylor Blau, Sep 18, 2020
  73. 09/13 bloom/diff: properly short-circuit on max_changesTaylor Blau, Sep 18, 2020
  74. Taylor BlauSep 18, 2020
  75. Taylor BlauSep 18, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.