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

Re: [PATCH v3 03/10] bloom: fix logic in get_bloom_filter()

From
Derrick Stolee <stolee@gmail.com>
Date
Jun 29, 2020, 13:02 UTC
Message-ID
<e998499b-6c27-e4c8-fa92-d83167ab41b6@gmail.com>
In-Reply-To
<20200627163335.GO2898@szeder.dev>
On 6/27/2020 12:33 PM, SZEDER Gábor wrote:
Show 66 quoted lines
> On Fri, Jun 26, 2020 at 12:30:29PM +0000, Derrick Stolee via GitGitGadget wrote:
>> From: Derrick Stolee <dstolee@microsoft.com>
>>
>> The get_bloom_filter() method is a bit complicated in some parts where
>> it does not need to be. In particular, it needs to return a NULL filter
>> only when compute_if_not_present is zero AND the filter data cannot be
>> loaded from a commit-graph file. This currently happens by accident
>> because the commit-graph does not load changed-path Bloom filters from
>> an existing commit-graph when writing a new one. This will change in a
>> later patch.
>>
>> Also clean up some style issues while we are here.
>>
>> Helped-by: René Scharfe <l.s.r@web.de>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>> ---
>>  bloom.c | 14 ++++++--------
>>  1 file changed, 6 insertions(+), 8 deletions(-)
>>
>> diff --git a/bloom.c b/bloom.c
>> index c38d1cff0c..2af5389795 100644
>> --- a/bloom.c
>> +++ b/bloom.c
>> @@ -186,7 +186,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
>>  	struct diff_options diffopt;
>>  	int max_changes = 512;
>>  
>> -	if (bloom_filters.slab_size == 0)
>> +	if (!bloom_filters.slab_size)
>>  		return NULL;
>>
>>  	filter = bloom_filter_slab_at(&bloom_filters, c);
>> @@ -194,16 +194,14 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
>>  	if (!filter->data) {
>>  		load_commit_graph_info(r, c);
>>  		if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
>> -			r->objects->commit_graph->chunk_bloom_indexes) {
>> -			if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
>> -				return filter;
>> -			else
>> -				return NULL;
>> -		}
>> +		    r->objects->commit_graph->chunk_bloom_indexes)
>> +			load_bloom_filter_from_graph(r->objects->commit_graph, filter, c);
>>  	}
>>  
>> -	if (filter->data || !compute_if_not_present)
>> +	if (filter->data)
>>  		return filter;
>> +	if (!compute_if_not_present)
>> +		return NULL;
> 
> Some callers of get_bloom_filter() invoke it with
> compute_if_not_present=0, but are not prepared to handle a NULL return
> value and dereference it right away:
> 
>   write_graph_chunk_bloom_indexes():
> 
>                 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
>                 cur_pos += filter->len;
> 
>   write_graph_chunk_bloom_data():
> 
>                 struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
>                 display_progress(progress, ++i);
>                 hashwrite(f, filter->data, filter->len * sizeof(unsigned char));

In theory, these _should_ be safe, because we already computed the filters in an earlier step, right? We should have generated the filter and populated it in the slab.

Show 17 quoted lines
> I don't know whether this was an issue before, but I didn't really
> tried.  Unfortunately, starting with this patch this causes
> segmentation faults basically in all real repositories I use for
> testing.
> 
>   expecting success of 9999.1 'test': 
>           for i in $(test_seq 1 513)
>           do
>                   >file-$i || return 1
>           done &&
>           git add file-* &&
>           git commit -q -m one &&
>   
>           git commit-graph write --reachable --changed-paths
>   
>   Segmentation fault
>   not ok 1 - test

However, you are demonstrating a failure that doesn't appear in our test suite. I was able to reproduce it.

I can confirm that this patch causes a SIGSEGV when writing the commit-graph in the Git repository, too.

So, what is wrong with my earlier assumption? There are two problems.

The thing I notice is that an empty filter (no changes with respect to the first parent) will have NULL filter->data, so we are returning NULL instead of a correctly-empty filter (with len zero).

But what you are hitting here is the max number of changes limit. That also returns a NULL filter, because we mark the filter as "TOO LARGE" to store. We store that as a zero-length filter.

The following fixup corrects the bug and adds a test similar to yours, but with extra care around ensuring the revision walk still works appropriately for that large commit.

In the next version, I will include more in the commit message about these side-effect changes, especially around the stats for zero-length filters. The trace2 message will no longer differentiate between zero-length filters and NULL filters.

Thanks, -Stolee

-- >8 --
From f9867adc5de8a072f41b91fd6cd87edfcc92e05e Mon Sep 17 00:00:00 2001
From: Derrick Stolee <dstolee@microsoft.com>
Date: Mon, 29 Jun 2020 08:52:33 -0400
Subject: [PATCH] fixup! bloom: fix logic in get_bloom_filter()
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c       |  8 ++++++--
 revision.c           |  7 -------
 t/t4216-log-bloom.sh | 24 ++++++++++++++++++++++--
 3 files changed, 28 insertions(+), 11 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index a0766a86f5..6752916c1a 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1108,7 +1108,8 @@ static int write_graph_chunk_bloom_indexes(struct hashfile *f,
 
 	while (list < last) {
 		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
-		cur_pos += filter->len;
+		size_t len = filter ? filter->len : 0;
+		cur_pos += len;
 		display_progress(progress, ++i);
 		hashwrite_be32(f, cur_pos);
 		list++;
@@ -1154,8 +1155,11 @@ static int write_graph_chunk_bloom_data(struct hashfile *f,
 
 	while (list < last) {
 		struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
+		size_t len = filter ? filter->len : 0;
 		display_progress(progress, ++i);
-		hashwrite(f, filter->data, filter->len * sizeof(unsigned char));
+
+		if (len)
+			hashwrite(f, filter->data, len * sizeof(unsigned char));
 		list++;
 	}
 
diff --git a/revision.c b/revision.c
index b40bc5b51b..b9118001f9 100644
--- a/revision.c
+++ b/revision.c
@@ -633,7 +633,6 @@ static unsigned int count_bloom_filter_maybe;
 static unsigned int count_bloom_filter_definitely_not;
 static unsigned int count_bloom_filter_false_positive;
 static unsigned int count_bloom_filter_not_present;
-static unsigned int count_bloom_filter_length_zero;
 
 static void trace2_bloom_filter_statistics_atexit(void)
 {
@@ -641,7 +640,6 @@ static void trace2_bloom_filter_statistics_atexit(void)
 
 	jw_object_begin(&jw, 0);
 	jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present);
-	jw_object_intmax(&jw, "zero_length_filter", count_bloom_filter_length_zero);
 	jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe);
 	jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not);
 	jw_object_intmax(&jw, "false_positive", count_bloom_filter_false_positive);
@@ -765,11 +763,6 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 		return -1;
 	}
 
-	if (!filter->len) {
-		count_bloom_filter_length_zero++;
-		return -1;
-	}
-
 	for (j = 0; result && j < revs->bloom_keys_nr; j++) {
 		result = bloom_filter_contains(filter,
 					       &revs->bloom_keys[j],
diff --git a/t/t4216-log-bloom.sh b/t/t4216-log-bloom.sh
index d7dd717347..4892364e74 100755
--- a/t/t4216-log-bloom.sh
+++ b/t/t4216-log-bloom.sh
@@ -60,7 +60,7 @@ setup () {
 
 test_bloom_filters_used () {
 	log_args=$1
-	bloom_trace_prefix="statistics:{\"filter_not_present\":0,\"zero_length_filter\":0,\"maybe\""
+	bloom_trace_prefix="statistics:{\"filter_not_present\":0,\"maybe\""
 	setup "$log_args" &&
 	grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
 	test_cmp log_wo_bloom log_w_bloom &&
@@ -146,7 +146,7 @@ test_expect_success 'setup - add commit-graph to the chain with Bloom filters' '
 
 test_bloom_filters_used_when_some_filters_are_missing () {
 	log_args=$1
-	bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"zero_length_filter\":0,\"maybe\":6,\"definitely_not\":8"
+	bloom_trace_prefix="statistics:{\"filter_not_present\":3,\"maybe\":6,\"definitely_not\":8"
 	setup "$log_args" &&
 	grep -q "$bloom_trace_prefix" "$TRASH_DIRECTORY/trace.perf" &&
 	test_cmp log_wo_bloom log_w_bloom
@@ -171,4 +171,24 @@ test_expect_success 'persist filter settings' '
 	grep "{\"hash_version\":1,\"num_hashes\":9,\"bits_per_entry\":15}" trace2-auto.txt
 '
 
+test_expect_success 'correctly report changes over limit' '
+	git init 513changes &&
+	(
+		cd 513changes &&
+		for i in $(test_seq 1 513)
+		do
+			echo $i >file$i.txt || return 1
+		done &&
+		git add . &&
+		git commit -m "files" &&
+		git commit-graph write --reachable --changed-paths &&
+		for i in $(test_seq 1 513)
+		do
+			git -c core.commitGraph=false log -- file$i.txt >expect &&
+			git log -- file$i.txt >actual &&
+			test_cmp expect actual || return 1
+		done
+	)
+'
+
 test_done
\ No newline at end of file

-- 
2.27.0.203.gf402ea6816
Previous: SZEDER GáborNext: Derrick Stolee via GitGitGadget
Message 53 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.