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

Re: [PATCH v4 04/10] commit-graph: persist existence of changed-paths

From
Taylor Blau <me@ttaylorr.com>
Date
Oct 15, 2020, 21:41 UTC
Message-ID
<20201015214111.GA2176154@nand.local>
In-Reply-To
<20201015132147.GB24954@szeder.dev>
On Thu, Oct 15, 2020 at 03:21:47PM +0200, SZEDER Gábor wrote:
Show 8 quoted lines
> As pointed out in my original bug report [1], modified path Bloom
> filters are computed with hardcoded settings in
> bloom.c:get_bloom_filter().  Since this patch does not touch bloom.c
> at all, it still computes Bloom filters with those hardcoded settings,
> and, consequently, despite the commit message's claims, it does not
> persist the settings in the existing commit-graph.
>
> [1] https://public-inbox.org/git/20200619140230.GB22200@szeder.dev/

Right. It is worth mentioning here (as you do below) that this was fixed as of 9a7a9ed10d (bloom: use provided 'struct bloom_filter_settings', 2020-09-16).

Show 12 quoted lines
> > Use the trace2 API to signal the settings used during the write, and
> > check that output in a test after manually adjusting the correct bytes
> > in the commit-graph file.
>
> This test is insufficient, as it only checks what settings trace2
> believes the Bloom filters are computed with, not what settings they
> are actually computed with; that's why it succeeded while the bug
> whose absence it was supposed to ensure was still there.
>
> More robust tests should instead look at what actually gets written to
> the commit-graph, and how that is interpreted during pathspec-limited
> revision walks.

Thanks for the test! That saved me a little bit of work trying to set up the scenario you're describing in a reproducible way. I think that the third test can be fixed relatively easily. The crux of the issue there is that we are computing Bloom filters for commits, some of which already had Bloom filters computed in an earlier layer, but with different settings than the one that we're using to write the current layer.

So, we need to be more aggressively checking the Bloom filter settings in any layer we want to reuse a Bloom filter out of before reusing it verbatim in the current layer. The patch below the scissors line is sufficient to do that, and it causes the third test to start passing.

...But, teaching the revision machinery how to handle a walk through commits in multiple commit-graph layers with incompatible Bloom filter settings is trickier. Right now we compute all of the Bloom keys up front using the Bloom filter settings in the top layer. I think we'd probably want to change this to lazily compute those keys by:

  - Keeping around the contents of the Bloom keys, i.e., the pathspecs
    themselves.
  - Keeping a hashmap from Bloom filter settings to computed Bloom keys
    corresponding to those settings.
  - Lazily filling in that hashmap as we traverse through different
    commits.

At least, that's the best way that I can think to do it. It does get kind of slow, though; we'd have to scan every commit graph layer at each commit in the worst case to find the actual 'struct commit_graph *' in order to get its Bloom filter settings. So, I think that's sort of show-stoppingly slow, and that we should probably think more deeply about it before taking up that direction.

Maybe Stolee has some better thoughts about how we can quickly go from a commit to either (a) the commit-graph struct that that commit is stored in, or (b) the Bloom filter settings belonging to that struct.

Thanks, Taylor

--- >8 ---
Subject: [PATCH] bloom: recompute filters with incompatible settings
---
 bloom.c        | 21 +++++++++++++++++++--
 commit-graph.c |  4 ++--
 2 files changed, 21 insertions(+), 4 deletions(-)
diff --git a/bloom.c b/bloom.c
index 68c73200a5..30da128474 100644
--- a/bloom.c
+++ b/bloom.c
@@ -30,7 +30,8 @@ static inline unsigned char get_bitmask(uint32_t pos)

 static int load_bloom_filter_from_graph(struct commit_graph *g,
 					struct bloom_filter *filter,
-					struct commit *c)
+					struct commit *c,
+					const struct bloom_filter_settings *settings)
 {
 	uint32_t lex_pos, start_index, end_index;
 	uint32_t graph_pos = commit_graph_position(c);
@@ -42,6 +43,21 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,
 	if (!g->chunk_bloom_indexes)
 		return 0;

+	if (settings) {
+		struct bloom_filter_settings *graph_settings = g->bloom_filter_settings;
+		/*
+		 * Check that the settings used to generate new Bloom filters is
+		 * compatible with the settings Bloom filters in this
+		 * commit-graph layer were generated with.
+		 */
+		if (settings->hash_version != graph_settings->hash_version)
+			return 0;
+		if (settings->num_hashes != graph_settings->num_hashes)
+			return 0;
+		if (settings->bits_per_entry != graph_settings->bits_per_entry)
+			return 0;
+	}
+
 	lex_pos = graph_pos - g->num_commits_in_base;

 	end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
@@ -205,7 +221,8 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 	if (!filter->data) {
 		load_commit_graph_info(r, c);
 		if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)
-			load_bloom_filter_from_graph(r->objects->commit_graph, filter, c);
+			load_bloom_filter_from_graph(r->objects->commit_graph,
+						     filter, c, settings);
 	}

 	if (filter->data && filter->len)
diff --git a/commit-graph.c b/commit-graph.c
index cb042bdba8..afe14af2a3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1188,7 +1188,7 @@ static int write_graph_chunk_bloom_indexes(struct hashfile *f,
 	uint32_t cur_pos = 0;

 	while (list < last) {
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		struct bloom_filter *filter = get_or_compute_bloom_filter(ctx->r, *list, 0, ctx->bloom_settings, NULL);
 		size_t len = filter ? filter->len : 0;
 		cur_pos += len;
 		display_progress(ctx->progress, ++ctx->progress_cnt);
@@ -1228,7 +1228,7 @@ static int write_graph_chunk_bloom_data(struct hashfile *f,
 	hashwrite_be32(f, ctx->bloom_settings->bits_per_entry);

 	while (list < last) {
-		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list);
+		struct bloom_filter *filter = get_or_compute_bloom_filter(ctx->r, *list, 0, ctx->bloom_settings, NULL);
 		size_t len = filter ? filter->len : 0;

 		display_progress(ctx->progress, ++ctx->progress_cnt);
--
2.29.0.rc1.dirty
Previous: SZEDER GáborNext: Derrick Stolee
Message 72 of 76 in “More commit-graph/Bloom filter improvements”
  1. 0/8 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jun 15, 2020
  2. 2/8 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jun 15, 2020
  3. René ScharfeJun 18, 2020
  4. 1/8 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jun 15, 2020
  5. René ScharfeJun 18, 2020
  6. Derrick StoleeJun 19, 2020
  7. 3/8 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jun 15, 2020
  8. René ScharfeJun 18, 2020
  9. 6/8 bloom: enforce a minimum size of 8 bytesDerrick Stolee via GitGitGadget, Jun 15, 2020
  10. 7/8 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jun 15, 2020
  11. 8/8 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jun 15, 2020
  12. 5/8 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jun 15, 2020
  13. René ScharfeJun 18, 2020
  14. René ScharfeJun 19, 2020
  15. Taylor BlauJun 19, 2020
  16. Taylor BlauJun 19, 2020
  17. Derrick StoleeJun 23, 2020
  18. 4/8 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jun 15, 2020
  19. Junio C HamanoJun 17, 2020
  20. Derrick StoleeJun 18, 2020
  21. 00/11 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jun 23, 2020
  22. 01/11 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jun 23, 2020
  23. 03/11 bloom: get_bloom_filter() cleanupsDerrick Stolee via GitGitGadget, Jun 23, 2020
  24. René ScharfeJun 25, 2020
  25. 02/11 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jun 23, 2020
  26. 04/11 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jun 23, 2020
  27. 05/11 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jun 23, 2020
  28. René ScharfeJun 25, 2020
  29. 06/11 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jun 23, 2020
  30. René ScharfeJun 25, 2020
  31. Derrick StoleeJun 25, 2020
  32. 08/11 revision.c: fix whitespaceDerrick Stolee via GitGitGadget, Jun 23, 2020
  33. 09/11 revision: empty pathspecs should not use Bloom filtersTaylor Blau via GitGitGadget, Jun 23, 2020
  34. 10/11 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jun 23, 2020
  35. René ScharfeJun 25, 2020
  36. Derrick StoleeJun 25, 2020
  37. SZEDER GáborJun 26, 2020
  38. Derrick StoleeJun 26, 2020
  39. 11/11 bloom: enforce a minimum size of 8 bytesDerrick Stolee via GitGitGadget, Jun 23, 2020
  40. 07/11 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jun 23, 2020
  41. René ScharfeJun 25, 2020
  42. Derrick StoleeJun 25, 2020
  43. Junio C HamanoJun 24, 2020
  44. Derrick StoleeJun 24, 2020
  45. Junio C HamanoJun 25, 2020
  46. Derrick StoleeJun 25, 2020
  47. Junio C HamanoJun 25, 2020
  48. 00/10 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jun 26, 2020
  49. 02/10 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jun 26, 2020
  50. 01/10 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jun 26, 2020
  51. 03/10 bloom: fix logic in get_bloom_filter()Derrick Stolee via GitGitGadget, Jun 26, 2020
  52. SZEDER GáborJun 27, 2020
  53. Derrick StoleeJun 29, 2020
  54. 04/10 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jun 26, 2020
  55. 05/10 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jun 26, 2020
  56. 06/10 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jun 26, 2020
  57. 07/10 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jun 26, 2020
  58. 10/10 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jun 26, 2020
  59. 09/10 revision: empty pathspecs should not use Bloom filtersTaylor Blau via GitGitGadget, Jun 26, 2020
  60. 08/10 revision.c: fix whitespaceDerrick Stolee via GitGitGadget, Jun 26, 2020
  61. 00/10 More commit-graph/Bloom filter improvementsDerrick Stolee via GitGitGadget, Jul 1, 2020
  62. 01/10 commit-graph: place bloom_settings in contextDerrick Stolee via GitGitGadget, Jul 1, 2020
  63. 02/10 commit-graph: change test to die on parse, not loadDerrick Stolee via GitGitGadget, Jul 1, 2020
  64. 03/10 bloom: fix logic in get_bloom_filter()Derrick Stolee via GitGitGadget, Jul 1, 2020
  65. 05/10 commit-graph: unify the signatures of all write_graph_chunk_*() functionsSZEDER Gábor via GitGitGadget, Jul 1, 2020
  66. 06/10 commit-graph: simplify chunk writes into loopSZEDER Gábor via GitGitGadget, Jul 1, 2020
  67. 07/10 commit-graph: check chunk sizes after writingSZEDER Gábor via GitGitGadget, Jul 1, 2020
  68. 10/10 commit-graph: check all leading directories in changed path Bloom filtersSZEDER Gábor via GitGitGadget, Jul 1, 2020
  69. 09/10 revision: empty pathspecs should not use Bloom filtersTaylor Blau via GitGitGadget, Jul 1, 2020
  70. 04/10 commit-graph: persist existence of changed-pathsDerrick Stolee via GitGitGadget, Jul 1, 2020
  71. SZEDER GáborOct 15, 2020
  72. Taylor BlauOct 15, 2020
  73. Derrick StoleeOct 16, 2020
  74. Taylor BlauOct 16, 2020
  75. Derrick StoleeOct 16, 2020
  76. 08/10 revision.c: fix whitespaceDerrick Stolee via GitGitGadget, Jul 1, 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.