Re: [PATCH v3 13/20] commit-graph: verify generation number

[Derrick Stolee <stolee@gmail.com>]

On 6/2/2018 8:23 AM, Jakub Narebski wrote:
> Derrick Stolee <dstolee@microsoft.com> writes:
>
>> While iterating through the commit parents, perform the generation
>> number calculation and compare against the value stored in the
>> commit-graph.
> All right, that's good.
>
> What about commit-graph files that have GENERATION_NUMBER_ZERO for all
> its commits (because we verify single commit-graph file only, there
> wouldn't be GENERATION_NUMBER_ZERO mixed with non-zero generation
> numbers)?
>
> Unless we can assume that no commit-graph file in the wild would have
> GENERATION_NUMBER_ZERO.

I was expecting that we would not have files in the wild with 
GENERATION_NUMBER_ZERO, but it looks like 2.18 will create files like 
that. I'll put in logic to verify "all are GENERATION_NUMBER_ZERO or all 
have 'correct' generation number".

>
>> The tests demonstrate that having a different set of parents affects
>> the generation number calculation, and this value propagates to
>> descendants. Hence, we drop the single-line condition on the output.
> I don't understand what part of changes this paragraph of the commit
> message refers to.
>
> Anyway, changing parents may not lead to changed generation numbers;
> take for example commit with single parent, which we change to other
> commit with the same generation number.

The tests introduced in the previous commit change the parent list, 
which then changes the generation number in some cases (the stored 
generation number doesn't match the generation number computed based on 
the loaded parents). Since we report as many errors as possible (instead 
of failing on first error) those tests would fail if we say "the _only_ 
error should be the parent list". (This comes up again when we report 
the hash is incorrect, which would appear in every test.)

The test introduced in this commit only changes the generation number, 
so that test will have the one error.

>
>> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>> ---
>>   commit-graph.c          | 18 ++++++++++++++++++
>>   t/t5318-commit-graph.sh |  6 ++++++
> Sidenote: I have just realized that it may be better to put
> validation-related tests into different test file.
>
>>   2 files changed, 24 insertions(+)
>>
>> diff --git a/commit-graph.c b/commit-graph.c
>> index fff22dc0c3..ead92460c1 100644
>> --- a/commit-graph.c
>> +++ b/commit-graph.c
>> @@ -922,6 +922,7 @@ int verify_commit_graph(struct commit_graph *g)
>>   	for (i = 0; i < g->num_commits; i++) {
>>   		struct commit *graph_commit, *odb_commit;
>>   		struct commit_list *graph_parents, *odb_parents;
>> +		uint32_t max_generation = 0;
>>   
>>   		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
>>   
>> @@ -956,6 +957,9 @@ int verify_commit_graph(struct commit_graph *g)
>>   					     oid_to_hex(&graph_parents->item->object.oid),
>>   					     oid_to_hex(&odb_parents->item->object.oid));
>>   
>> +			if (graph_parents->item->generation > max_generation)
>> +				max_generation = graph_parents->item->generation;
>> +
> All right, that calculates the maximum of generation number of commit
> parents.
>
>>   			graph_parents = graph_parents->next;
>>   			odb_parents = odb_parents->next;
>>   		}
>> @@ -963,6 +967,20 @@ int verify_commit_graph(struct commit_graph *g)
>>   		if (odb_parents != NULL)
>>   			graph_report("commit-graph parent list for commit %s terminates early",
>>   				     oid_to_hex(&cur_oid));
>> +
>> +		/*
>> +		 * If one of our parents has generation GENERATION_NUMBER_MAX, then
>> +		 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
>> +		 * extra logic in the following condition.
>> +		 */
> Nice trick.
>
>> +		if (max_generation == GENERATION_NUMBER_MAX)
>> +			max_generation--;
> What about GENERATION_NUMBER_ZERO?
>
>> +
>> +		if (graph_commit->generation != max_generation + 1)
>> +			graph_report("commit-graph generation for commit %s is %u != %u",
>> +				     oid_to_hex(&cur_oid),
>> +				     graph_commit->generation,
>> +				     max_generation + 1);
> I think we should also check that generation numbers do not exceed
> GENERATION_NUMBER_MAX... unless it is already taken care of?

We get that for free. First, the condition above would fail for at least 
one commit. Second, we literally cannot store a value larger than 
GENERATION_NUMBER_MAX in the commit-graph as there are only 30 bits 
dedicated to the generation number.

>
>>   	}
>>   
>>   	return verify_commit_graph_error;
>> diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
>> index 12f0d7f54d..673b0d37d5 100755
>> --- a/t/t5318-commit-graph.sh
>> +++ b/t/t5318-commit-graph.sh
>> @@ -272,6 +272,7 @@ GRAPH_BYTE_COMMIT_TREE=$GRAPH_COMMIT_DATA_OFFSET
>>   GRAPH_BYTE_COMMIT_PARENT=`expr $GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN`
>>   GRAPH_BYTE_COMMIT_EXTRA_PARENT=`expr $GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 4`
>>   GRAPH_BYTE_COMMIT_WRONG_PARENT=`expr $GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 3`
>> +GRAPH_BYTE_COMMIT_GENERATION=`expr $GRAPH_COMMIT_DATA_OFFSET + $HASH_LEN + 8`
>>   
>>   # usage: corrupt_graph_and_verify <position> <data> <string>
>>   # Manipulates the commit-graph file at the position
>> @@ -366,4 +367,9 @@ test_expect_success 'detect incorrect tree OID' '
>>   		"commit-graph parent for"
>>   '
>>   
>> +test_expect_success 'detect incorrect generation number' '
>> +	corrupt_graph_and_verify $GRAPH_BYTE_COMMIT_GENERATION "\01" \
> I assume that you have checked that it actually corrupts generation
> number (without affecting commit date).
>
>> +		"generation"
> A very minor nitpick: Not "generation for commit"?
>
>> +'
>> +
>>   test_done