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

Re: [RFC/PATCH] commit-graph: verify swapped zero/non-zero generation cases

From
Taylor Blau <me@ttaylorr.com>
Date
Aug 10, 2023, 17:44 UTC
Message-ID
<ZNUiEXF5CP6WMk9A@nand.local>
In-Reply-To
<ZNUJq2nFEDHwrF0U@nand.local>
On Thu, Aug 10, 2023 at 12:00:43PM -0400, Taylor Blau wrote:
Show 37 quoted lines
> > There's a matching GENERATION_NUMBER_EXISTS value, which in theory would
> > be used to find the case that we see the entries in the opposite order:
> >
> >   1. When we see an entry with a non-zero generation, we set the
> >      generation_zero flag to GENERATION_NUMBER_EXISTS.
> >
> >   2. When we later see an entry with a zero generation, we complain if
> >      the flag is GENERATION_NUMBER_EXISTS.
> >
> > But that doesn't work; step 2 is implemented, but there is no step 1. We
> > never use NUMBER_EXISTS at all, and Coverity rightly complains that step
> > 2 is dead code.
>
> So I think the missing part is setting GENERATION_NUMBER_EXISTS when we
> have a non-zero generation number from the commit-graph, but have
> generation_zero set to GENERATION_ZERO_EXISTS (IOW, we have seen at
> least one commit with generation number 0).
>
> --- 8< ---
> diff --git a/commit-graph.c b/commit-graph.c
> index 0aa1640d15..935bc15440 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -2676,9 +2676,11 @@ static int verify_one_commit_graph(struct repository *r,
>  				graph_report(_("commit-graph has generation number zero for commit %s, but non-zero elsewhere"),
>  					     oid_to_hex(&cur_oid));
>  			generation_zero = GENERATION_ZERO_EXISTS;
> -		} else if (generation_zero == GENERATION_ZERO_EXISTS)
> +		} else if (generation_zero == GENERATION_ZERO_EXISTS) {
>  			graph_report(_("commit-graph has non-zero generation number for commit %s, but zero elsewhere"),
>  				     oid_to_hex(&cur_oid));
> +			generation_zero = GENERATION_NUMBER_EXISTS;
> +		}
>
>  		if (generation_zero == GENERATION_ZERO_EXISTS)
>  			continue;
> --- >8 ---

OK, I investigated this a little bit more and now I think I understand fully what's going on here.

There are a couple of things wrong with the diff that I posted above. First, it has a logic error that we should set GENERATION_NUMBER_EXISTS when we have a non-zero generation number from the graph, regardless of whether or not GENERATION_ZERO_EXISTS is set (like how it is done in your patch).

But more importantly, we'll never end up in the first arm of that conditional as-is (the one that fires for when we see a generation number of zero) as a consequence of 2ee11f7261 (commit-graph: return generation from memory, 2023-03-20), which only returns non-zero generation numbers (or GENERATION_NUMBER_INFINITY, which is also non-zero).

I think you want something like `commit_graph_generation()` that returns whatever is in `data->generation` regardless of whether or not it is zero valued. You'd then want to use that function instead of calling commit_graph_generation() directly.

Show 9 quoted lines
> > So I kind of wonder if there's something I'm not getting here. Coverity
> > is definitely right that our "step 2" is dead code (because we never set
> > NUMBER_EXISTS). But I'm not sure if we should be deleting it, or trying
> > to fix an underlying bug.
>
> I think that above is correct in that we should be fixing an underlying
> bug. But the fact that this isn't caught by our existing tests indicates
> that there is a gap in coverage. Let me see if I can find a test case
> that highlights this bug...

Doing the above allows me to write these two tests on top of your patch, which both pass:

--- &< ---
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 4df76173a8..8e96471b34 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -450,14 +450,15 @@ GRAPH_BYTE_FANOUT2=$(($GRAPH_FANOUT_OFFSET + 4 * 255))
 GRAPH_OID_LOOKUP_OFFSET=$(($GRAPH_FANOUT_OFFSET + 4 * 256))
 GRAPH_BYTE_OID_LOOKUP_ORDER=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN * 8))
 GRAPH_BYTE_OID_LOOKUP_MISSING=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN * 4 + 10))
+GRAPH_COMMIT_DATA_WIDTH=$(($HASH_LEN + 16))
 GRAPH_COMMIT_DATA_OFFSET=$(($GRAPH_OID_LOOKUP_OFFSET + $HASH_LEN * $NUM_COMMITS))
 GRAPH_BYTE_COMMIT_TREE=$GRAPH_COMMIT_DATA_OFFSET
 GRAPH_BYTE_COMMIT_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN))
 GRAPH_BYTE_COMMIT_EXTRA_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 4))
 GRAPH_BYTE_COMMIT_WRONG_PARENT=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 3))
 GRAPH_BYTE_COMMIT_GENERATION=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 11))
+GRAPH_BYTE_COMMIT_GENERATION_LAST=$(($GRAPH_BYTE_COMMIT_GENERATION + $(($NUM_COMMITS - 1)) * $GRAPH_COMMIT_DATA_WIDTH))
 GRAPH_BYTE_COMMIT_DATE=$(($GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 12))
-GRAPH_COMMIT_DATA_WIDTH=$(($HASH_LEN + 16))
 GRAPH_OCTOPUS_DATA_OFFSET=$(($GRAPH_COMMIT_DATA_OFFSET + \
 			     $GRAPH_COMMIT_DATA_WIDTH * $NUM_COMMITS))
 GRAPH_BYTE_OCTOPUS=$(($GRAPH_OCTOPUS_DATA_OFFSET + 4))
@@ -596,11 +597,6 @@ test_expect_success 'detect incorrect generation number' '
 		"generation for commit"
 '

-test_expect_success 'detect incorrect generation number' '
-	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \
-		"commit-graph generation for commit"
-'
-
 test_expect_success 'detect incorrect commit date' '
 	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_DATE "\01" \
 		"commit date"
@@ -622,6 +618,16 @@ test_expect_success 'detect incorrect chunk count' '
 		$GRAPH_CHUNK_LOOKUP_OFFSET
 '

+test_expect_success 'detect mixed generation numbers (non-zero to zero)' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION_LAST "\0\0\0\0" \
+		"but non-zero elsewhere"
+'
+
+test_expect_success 'detect mixed generation numbers (zero to non-zero)' '
+	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\0\0\0\0" \
+		"but zero elsewhere"
+'
+
 test_expect_success 'git fsck (checks commit-graph when config set to true)' '
 	git -C full fsck &&
 	corrupt_graph_and_verify $GRAPH_BYTE_FOOTER "\00" \
--- >8 ---

Note that we remove the duplicate "detect incorrect generation number"
test, which was originally introduced in 1373e547f7 (commit-graph:
verify generation number, 2018-06-27), but was modified in 2ee11f7261.

That test is replaced by the latter "non-zero to zero" variant.

Thanks,
Taylor
Previous: Taylor BlauNext: Taylor Blau
Message 3 of 30 in “commit-graph: verify swapped zero/non-zero generation cases”
  1. commit-graph: verify swapped zero/non-zero generation casesJeff King, Aug 8, 2023
  2. Taylor BlauAug 10, 2023
  3. Taylor BlauAug 10, 2023
  4. 0/4 commit-graph: fsck zero/non-zero generation number fixesTaylor Blau, Aug 10, 2023
  5. 1/4 commit-graph: introduce `commit_graph_generation_from_graph()`Taylor Blau, Aug 10, 2023
  6. 2/4 commit-graph: verify swapped zero/non-zero generation casesTaylor Blau, Aug 10, 2023
  7. Junio C HamanoAug 10, 2023
  8. Jeff KingAug 11, 2023
  9. Taylor BlauAug 11, 2023
  10. 3/4 t/t5318-commit-graph.sh: test generation zero transitions during fsckTaylor Blau, Aug 10, 2023
  11. 4/4 commit-graph: invert negated conditionalTaylor Blau, Aug 10, 2023
  12. Jeff KingAug 11, 2023
  13. 0/5 commit-graph: fsck zero/non-zero generation number fixesTaylor Blau, Aug 11, 2023
  14. 1/5 commit-graph: introduce `commit_graph_generation_from_graph()`Taylor Blau, Aug 11, 2023
  15. 2/5 commit-graph: verify swapped zero/non-zero generation casesTaylor Blau, Aug 11, 2023
  16. 3/5 t/t5318-commit-graph.sh: test generation zero transitions during fsckTaylor Blau, Aug 11, 2023
  17. 4/5 commit-graph: invert negated conditional, extract to functionTaylor Blau, Aug 11, 2023
  18. 5/5 commit-graph: avoid repeated mixed generation number warningsTaylor Blau, Aug 11, 2023
  19. Jeff KingAug 11, 2023
  20. Junio C HamanoAug 11, 2023
  21. Jeff KingAug 17, 2023
  22. Taylor BlauAug 21, 2023
  23. 0/4 commit-graph: fsck zero/non-zero generation number fixesTaylor Blau, Aug 21, 2023
  24. 1/4 commit-graph: introduce `commit_graph_generation_from_graph()`Taylor Blau, Aug 21, 2023
  25. 2/4 commit-graph: verify swapped zero/non-zero generation casesTaylor Blau, Aug 21, 2023
  26. 3/4 t/t5318-commit-graph.sh: test generation zero transitions during fsckTaylor Blau, Aug 21, 2023
  27. 4/4 commit-graph: commit-graph: avoid repeated mixed generation number warningsTaylor Blau, Aug 21, 2023
  28. Jeff KingAug 21, 2023
  29. Junio C HamanoAug 21, 2023
  30. Taylor BlauAug 23, 2023

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.