Re: [PATCH 2/7] commit-graph: fix ordering bug in generation numbers

[Derrick Stolee <derrickstolee@github.com>]

On 2/24/2022 5:15 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> From: Derrick Stolee <derrickstolee@github.com>
>>
>> When computing the generation numbers for a commit-graph, we compute
>> the corrected commit dates and then check if their offsets from the
>> actual dates is too large to fit in the 32-bit Generation Data chunk.
>> However, there is a problem with this approach: if we have parsed the
>> generation data from the previous commit-graph, then we continue the
>> loop because the corrected commit date is already computed.
>>
>> It is incorrect to add an increment to num_generation_data_overflows
>> here, because we might start double-counting commits that are computed
>> because of the depth-first search walk from a commit with an earlier
>> OID.
>>
>> Instead, iterate over the full commit list at the end, checking the
>> offsets to see how many grow beyond the maximum value.
> 
> Hmph, I can see how the new code correctly counts the commits that
> require offsets that are too large, but I am not sure why the fix is
> needed.  The overall loop structure is

It is very subtle, which is why it took me a while to debug this
issue once I managed to trigger it.

>     for each commit ctx->commits.list[i]:
>         continue if generation number has been computed for it already

This is the critical line in the current version. This includes
"continue if the generation number was loaded from the previous
commit-graph file." This means we under-count when building from
an existing commit-graph with overflows.

If we insert an increment here, then we risk double-counting. I
should have described this better.

> 	set up a commit-list for depth first search
> 	while (we are still digging) {
> 		for each parent {
> 			if generation for the parent is not known yet:
> 				push it down and redo
> 			else
> 				compute max of parents' generation number
> 		}
>                 if (all parents' generation number is known) {
> 			set the generation number for ourselves
> 			count if we needed an offset that is too big
> 		}
> 	}
>     }
> 
> The only case where we may double-count near the end of inner loop I
> can think of is when we end up computing generation for the same
> commit in the while () loop.  But isn't that "we dig the same thing
> twice" by itself something we want to fix, regardless of the
> double-counting issue?

By "we dig the same thing twice" I think you mean "we look across
every edge in the commit-graph, and some commits have multiple
direct children." There is no way around this, but we do skip
recalculating generation numbers for parents that are already
computed.

> IOW,
> 
>>  				if (current->date && current->date > max_corrected_commit_date)
>>  					max_corrected_commit_date = current->date - 1;
>>  				commit_graph_data_at(current)->generation = max_corrected_commit_date + 1;
>> -
>> -				if (commit_graph_data_at(current)->generation - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
>> -					ctx->num_generation_data_overflows++;
>>  			}
>>  		}
>>  	}
> 
> here, before doing the assignment for the "current" commit's
> generation number, if we added
> 
> 		if (commit_graph_data_at(current)->generation !=
> 		    GENERATION_NUMBER_ZERO)
> 			BUG("why are we digging it twice?");
> 
> would it trigger?  If so, isn't that already a bug worth fixing?

This would not trigger, since 'current' did not have its
generation when adding to the stack and it could not possibly
have been added a second time when doing a depth-first search
from that commit.

> Perhaps avoiding the second round, perhaps like this, may be a
> better fix?
> 
> 	while (list) {
> 		struct commit *current = list->item;
> 		struct commit_list *parent;
> 		int all_parents_computed = 1;
> 		timestamp_t max_corrected_commit_date = 0;
> 
> +		if (commit_graph_data_at(current)->generation !=
> +		    GENERATION_NUMBER_ZERO) {
> +			pop_commit(&list);
> +			continue;
> +		}
> +
> 		for (parent = current->parents; parent; parent = parent->next) {
> 
> Or am I grossly misunderstanding why the original code is incorrect
> to have the counting at this place?

Hopefully I cleared up the issue earlier in my reply. Let me
know if this is still confusing.

Thanks,
-Stolee