Commit-graph: Generation Number v2 Fixes, v3 implementation

From: Derrick Stolee <[email protected]>

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.

commit-graph.c +7 -0

+
+	for (i = 0; i < ctx->commits.nr; i++) {
+		struct commit *c = ctx->commits.list[i];
+		timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
+		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
+			ctx->num_generation_data_overflows++;
+	}
 	stop_progress(&ctx->progress);
 }

t/t5318-commit-graph.sh +2 -2

index 2b05026cf6d..f9bffe38013 100755
@@ -467,10 +467,10 @@ test_expect_success 'warn on improper hash version' '
 	)
 '
 
-test_expect_success 'lower layers have overflow chunk' '
+test_expect_success TIME_IS_64BIT,TIME_T_IS_64BIT 'lower layers have overflow chunk' '
 	cd "$TRASH_DIRECTORY/full" &&
 	UNIX_EPOCH_ZERO="@0 +0000" &&
-	FUTURE_DATE="@2147483646 +0000" &&
+	FUTURE_DATE="@4147483646 +0000" &&
 	rm -f .git/objects/info/commit-graph &&
 	test_commit --date "$FUTURE_DATE" future-1 &&
 	test_commit --date "$UNIX_EPOCH_ZERO" old-1 &&

Quoted 14 lines · Derrick Stolee via GitGitGadget

From: Derrick Stolee <[email protected]>

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.

Quoted 2 lines

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

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

	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?

IOW,

commit-graph.c static void compute_generation_numbers(struct write_commit_graph_context *ctx) · line 1561

Quoted 9 lines

commit-graph.c +0 -3

 				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?

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;

(quoted diff) +6 -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?

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

Quoted 2 lines

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.

From: Derrick Stolee <[email protected]>

The 'read_generation_data' member of 'struct commit_graph' was introduced by 1fdc383c5 (commit-graph: use generation v2 only if entire chain does, 2021-01-16). The intention was to avoid using corrected commit dates if not all layers of a commit-graph had that data stored. The logic in validate_mixed_generation_chain() at that point incorrectly initialized read_generation_data to 1 if and only if the tip commit-graph contained the Corrected Commit Date chunk.

This was "fixed" in 448a39e65 (commit-graph: validate layers for generation data, 2021-02-02) to validate that read_generation_data was either non-zero for all layers, or it would set read_generation_data to zero for all layers.

The problem here is that read_generation_data is not initialized to be non-zero anywhere!

This change initializes read_generation_data immediately after the chunk is parsed, so each layer will have its value present as soon as possible.

The read_generation_data member is used in fill_commit_graph_info() to determine if we should use the corrected commit date or the topological levels stored in the Commit Data chunk. Due to this bug, all previous versions of Git were defaulting to topological levels in all cases!

This can be measured with some performance tests. Using the Linux kernel as a testbed, I generated a complete commit-graph containing corrected commit dates and tested the 'new' version against the previous, 'old' version.

First, rev-list with --topo-order demonstrates a 26% improvement using corrected commit dates:

hyperfine \
	-n "old" "$OLD_GIT rev-list --topo-order -1000 v3.6" \
	-n "new" "$NEW_GIT rev-list --topo-order -1000 v3.6" \
	--warmup=10

Benchmark 1: old

  Time (mean ± σ):      57.1 ms ±   3.1 ms
  Range (min … max):    52.9 ms …  62.0 ms    55 runs

Benchmark 2: new

  Time (mean ± σ):      45.5 ms ±   3.3 ms
  Range (min … max):    39.9 ms …  51.7 ms    59 runs

Summary
'new' ran

    1.26 ± 0.11 times faster than 'old'

These performance improvements are due to the algorithmic improvements given by walking fewer commits due to the higher cutoffs from corrected commit dates.

However, this comes at a cost. The additional I/O cost of parsing the corrected commit dates is visible in case of merge-base commands that do not reduce the overall number of walked commits.

hyperfine \
        -n "old" "$OLD_GIT merge-base v4.8 v4.9" \
        -n "new" "$NEW_GIT merge-base v4.8 v4.9" \
        --warmup=10

Benchmark 1: old
Time (mean ± σ): 110.4 ms ± 6.4 ms
Range (min … max): 96.0 ms … 118.3 ms 25 runs

Benchmark 2: new
Time (mean ± σ): 150.7 ms ± 1.1 ms
Range (min … max): 149.3 ms … 153.4 ms 19 runs

Summary
'old' ran

    1.36 ± 0.08 times faster than 'new'

Performance issues like this are what motivated 702110aac (commit-graph:
use config to specify generation type, 2021-02-25).

In the future, we could fix this performance problem by inserting the corrected commit date offsets into the Commit Date chunk instead of having that data in an extra chunk.

Signed-off-by Derrick Stolee <[email protected]>

---
 commit-graph.c                |  3 +++
 t/t4216-log-bloom.sh          |  2 +-
 t/t5318-commit-graph.sh       | 14 ++++++++++++--
 t/t5324-split-commit-graph.sh |  9 +++++++--
 4 files changed, 23 insertions(+), 5 deletions(-)

commit-graph.c +0 -0

index a19bd96c2ee..8e52bb09552 100644

Quoted 1 line · Derrick Stolee via GitGitGadget

From: Derrick Stolee <[email protected]>

Quoted 5 lines

commit-graph.c +0 -0

index a19bd96c2ee..8e52bb09552 100644

commit-graph.c struct commit_graph *parse_commit_graph(struct repository *r, · line 415

Quoted 9 lines

commit-graph.c +3 -0

@@ -407,6 +407,9 @@ struct commit_graph *parse_commit_graph(struct repository *r,
 			&graph->chunk_generation_data);
 		pair_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,
 			&graph->chunk_generation_data_overflow);
+
+		if (graph->chunk_generation_data)
+			graph->read_generation_data = 1;
 	}
 
 	if (r->settings.commit_graph_read_changed_paths) {

I wanted to test your changes because they seem quite exciting in the context of my work as well, but this commit seems to uncover a bug with how we handle overflows. I originally triggered the bug when trying to do a mirror-fetch, but as it turns it seems to trigger now whenever the commit-graph is being read:

    $ git commit-graph verify
    fatal: commit-graph requires overflow generation data but has none

    $ git commit-graph write --split
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

    $ git commit-graph write --split=replace
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

I initially assumed this may be a bug with how we previously wrote the commit-graph, but removing all chains still reliably triggers it:

    $ rm -f objects/info/commit-graphs/*
    $ git commit-graph write --split
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Quoted 2 lines · Patrick Steinhardt

Quoted 1 line · Derrick Stolee via GitGitGadget

From: Derrick Stolee <[email protected]>

...

Quoted 40 lines

Quoted 5 lines

commit-graph.c +0 -0

index a19bd96c2ee..8e52bb09552 100644

commit-graph.c struct commit_graph *parse_commit_graph(struct repository *r, · line 415

Quoted 9 lines

commit-graph.c +3 -0

@@ -407,6 +407,9 @@ struct commit_graph *parse_commit_graph(struct repository *r,
 			&graph->chunk_generation_data);
 		pair_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW,
 			&graph->chunk_generation_data_overflow);
+
+		if (graph->chunk_generation_data)
+			graph->read_generation_data = 1;
 	}
 
 	if (r->settings.commit_graph_read_changed_paths) {

I wanted to test your changes because they seem quite exciting in the context of my work as well, but this commit seems to uncover a bug with how we handle overflows. I originally triggered the bug when trying to do a mirror-fetch, but as it turns it seems to trigger now whenever the commit-graph is being read:

    $ git commit-graph verify
    fatal: commit-graph requires overflow generation data but has none

    $ git commit-graph write --split
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

    $ git commit-graph write --split=replace
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

I initially assumed this may be a bug with how we previously wrote the commit-graph, but removing all chains still reliably triggers it:

    $ rm -f objects/info/commit-graphs/*
    $ git commit-graph write --split
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    fatal: commit-graph requires overflow generation data but has none

Quoted 8 lines

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Thanks for including this information. Just to be clear: did you include patch 4 in your tests, or not? Patch 4 includes a fix related to overflow values, so it would be helpful to know if you found a _different_ bug or if it is the same one.

Thanks,
-Stolee

Quoted 15 lines · Derrick Stolee

Quoted 8 lines · Patrick Steinhardt

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Thanks for including this information. Just to be clear: did you include patch 4 in your tests, or not? Patch 4 includes a fix related to overflow values, so it would be helpful to know if you found a _different_ bug or if it is the same one.

Quoted 2 lines

Thanks,
-Stolee

I initially only applied the first three patches, but after having hit the fatal error I also applied the rest of this series to have a look at whether it is indeed fixed already by one of your later patches. The error remains the same though.

Quoted 16 lines · Patrick Steinhardt

Quoted 15 lines · Derrick Stolee

Quoted 8 lines · Patrick Steinhardt

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Thanks for including this information. Just to be clear: did you include patch 4 in your tests, or not? Patch 4 includes a fix related to overflow values, so it would be helpful to know if you found a _different_ bug or if it is the same one.

Quoted 7 lines

Quoted 2 lines

Thanks,
-Stolee

I initially only applied the first three patches, but after having hit the fatal error I also applied the rest of this series to have a look at whether it is indeed fixed already by one of your later patches. The error remains the same though.

Thanks for this extra context. Is this a commit-graph that you wrote with the first three patches and then you get an error when reading it?

Do you get the same error when deleting that file and rewriting it with all patches included?

Thanks,
-Stolee

Quoted 25 lines · Derrick Stolee

Quoted 16 lines · Patrick Steinhardt

Quoted 15 lines · Derrick Stolee

Quoted 8 lines · Patrick Steinhardt

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Thanks for including this information. Just to be clear: did you include patch 4 in your tests, or not? Patch 4 includes a fix related to overflow values, so it would be helpful to know if you found a _different_ bug or if it is the same one.

Quoted 7 lines

Quoted 2 lines

Thanks,
-Stolee

I initially only applied the first three patches, but after having hit the fatal error I also applied the rest of this series to have a look at whether it is indeed fixed already by one of your later patches. The error remains the same though.

Quoted 8 lines

Thanks for this extra context. Is this a commit-graph that you wrote with the first three patches and then you get an error when reading it?

Do you get the same error when deleting that file and rewriting it with all patches included?

Thanks,
-Stolee

Yes, I do. I've applied all four patches from v2 on top of 715d08a9e5 (The eighth batch, 2022-02-25) and still get the same results:

    $ find objects/info/commit-graphs/
    objects/info/commit-graphs/
    objects/info/commit-graphs/graph-607e641165f3e83a82d5b14af4e611bf2a688f35.graph
    objects/info/commit-graphs/commit-graph-chain
    objects/info/commit-graphs/graph-5f357c7573c0075d42d82b28e660bc3eac01bfe8.graph
    objects/info/commit-graphs/graph-e0c12ead1b61c7c30720ae372e8a9f98d95dfb2d.graph
    objects/info/commit-graphs/graph-c96723b133c2d81106a01ecd7a8773bb2ef6c2e1.graph

     $ git commit-graph verify
    fatal: commit-graph requires overflow generation data but has none

     $ git commit-graph write
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    Expanding reachable commits in commit graph: 2197197, done.
    Finding extra edges in commit graph: 100% (2197197/2197197), done.
    fatal: commit-graph requires overflow generation data but has none

     $ rm -rf objects/info/commit-graphs/

     $ git commit-graph write
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    Expanding reachable commits in commit graph: 2197197, done.
    Finding extra edges in commit graph: 100% (2197197/2197197), done.
    fatal: commit-graph requires overflow generation data but has none)

So even generating them completely anew doesn't seem to generate the overflow generation data.

Patrick

Quoted 63 lines · Patrick Steinhardt

Quoted 25 lines · Derrick Stolee

Quoted 16 lines · Patrick Steinhardt

Quoted 15 lines · Derrick Stolee

Quoted 8 lines · Patrick Steinhardt

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Thanks for including this information. Just to be clear: did you include patch 4 in your tests, or not? Patch 4 includes a fix related to overflow values, so it would be helpful to know if you found a _different_ bug or if it is the same one.

Quoted 7 lines

Quoted 2 lines

Thanks,
-Stolee

I initially only applied the first three patches, but after having hit the fatal error I also applied the rest of this series to have a look at whether it is indeed fixed already by one of your later patches. The error remains the same though.

Quoted 8 lines

Thanks for this extra context. Is this a commit-graph that you wrote with the first three patches and then you get an error when reading it?

Do you get the same error when deleting that file and rewriting it with all patches included?

Thanks,
-Stolee

Yes, I do. I've applied all four patches from v2 on top of 715d08a9e5 (The eighth batch, 2022-02-25) and still get the same results:

    $ find objects/info/commit-graphs/
    objects/info/commit-graphs/
    objects/info/commit-graphs/graph-607e641165f3e83a82d5b14af4e611bf2a688f35.graph
    objects/info/commit-graphs/commit-graph-chain
    objects/info/commit-graphs/graph-5f357c7573c0075d42d82b28e660bc3eac01bfe8.graph
    objects/info/commit-graphs/graph-e0c12ead1b61c7c30720ae372e8a9f98d95dfb2d.graph
    objects/info/commit-graphs/graph-c96723b133c2d81106a01ecd7a8773bb2ef6c2e1.graph

     $ git commit-graph verify
    fatal: commit-graph requires overflow generation data but has none

     $ git commit-graph write
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    Expanding reachable commits in commit graph: 2197197, done.
    Finding extra edges in commit graph: 100% (2197197/2197197), done.
    fatal: commit-graph requires overflow generation data but has none

     $ rm -rf objects/info/commit-graphs/

     $ git commit-graph write
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    Expanding reachable commits in commit graph: 2197197, done.
    Finding extra edges in commit graph: 100% (2197197/2197197), done.
    fatal: commit-graph requires overflow generation data but has none)

Quoted 4 lines

So even generating them completely anew doesn't seem to generate the overflow generation data.

Patrick

I stand corrected. I forgot that the repository at hand was connected to another one via objects/info/alternates. If I prune commit-graphs from that alternate, too, then it works alright with your patches.

This makes me wonder how such a bugfix should be handled though. As this series is right now, users will be faced with repository corruption as soon as they upgrade their Git version to one that contains this patch series. This corruption needs manual action: they have to go into the repository, delete the commit-graphs and then optionally create new ones.

This is not a good user experience, and it's worse on the server-side where we now have a timeframe where all commit-graphs are potentially corrupt. This effectively leads to us being unable to serve those repos at all until we have rewritten the commit-graphs because all commands which make use of the commit-graph will now die:

    $ git log
    fatal: commit-graph requires overflow generation data but has none

So the question is whether this is a change that needs to be rolled out over multiple releases. First we'd get in the bug fix such that we write correct commit-graphs, and after this fix has been released we can also release the fix that starts to actually parse the generation. This ensures there's a grace period during which we can hopefully correct the data on-disk such that users are not faced with failures.

The better alternative would probably be to just gracefully handle commit-graphs which are corrupted in such a way. Can we maybe just continue to not parse generations in case we find that the commit-graph doesn't have overflow generation data?

This is more of a general issue though: commit-graphs are an auxiliary cache that is not required for proper operation at all. If we fail to parse it, then Git shouldn't die but instead fail gracefully just ignore it. Furthermore, if we notice that graphs are corrupt when we try to write new ones, we may just delete the corrupt versions automatically and generate completely new ones.

Quoted 64 lines · Patrick Steinhardt

Quoted 63 lines · Patrick Steinhardt

Quoted 25 lines · Derrick Stolee

Quoted 16 lines · Patrick Steinhardt

Quoted 15 lines · Derrick Stolee

Quoted 8 lines · Patrick Steinhardt

I haven't yet found the time to dig deeper into why this is happening. While the repository is publicly accessible at [1], unfortunately the bug seems to be triggered by a commit that's only kept alive by an internal reference.

Patrick

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Thanks for including this information. Just to be clear: did you include patch 4 in your tests, or not? Patch 4 includes a fix related to overflow values, so it would be helpful to know if you found a _different_ bug or if it is the same one.

Quoted 7 lines

Quoted 2 lines

Thanks,
-Stolee

I initially only applied the first three patches, but after having hit the fatal error I also applied the rest of this series to have a look at whether it is indeed fixed already by one of your later patches. The error remains the same though.

Quoted 8 lines

Thanks for this extra context. Is this a commit-graph that you wrote with the first three patches and then you get an error when reading it?

Do you get the same error when deleting that file and rewriting it with all patches included?

Thanks,
-Stolee

Yes, I do. I've applied all four patches from v2 on top of 715d08a9e5 (The eighth batch, 2022-02-25) and still get the same results:

    $ find objects/info/commit-graphs/
    objects/info/commit-graphs/
    objects/info/commit-graphs/graph-607e641165f3e83a82d5b14af4e611bf2a688f35.graph
    objects/info/commit-graphs/commit-graph-chain
    objects/info/commit-graphs/graph-5f357c7573c0075d42d82b28e660bc3eac01bfe8.graph
    objects/info/commit-graphs/graph-e0c12ead1b61c7c30720ae372e8a9f98d95dfb2d.graph
    objects/info/commit-graphs/graph-c96723b133c2d81106a01ecd7a8773bb2ef6c2e1.graph

     $ git commit-graph verify
    fatal: commit-graph requires overflow generation data but has none

     $ git commit-graph write
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    Expanding reachable commits in commit graph: 2197197, done.
    Finding extra edges in commit graph: 100% (2197197/2197197), done.
    fatal: commit-graph requires overflow generation data but has none

     $ rm -rf objects/info/commit-graphs/

     $ git commit-graph write
    Finding commits for commit graph among packed objects: 100% (10235119/10235119), done.
    Expanding reachable commits in commit graph: 2197197, done.
    Finding extra edges in commit graph: 100% (2197197/2197197), done.
    fatal: commit-graph requires overflow generation data but has none)

Quoted 8 lines

Quoted 4 lines

So even generating them completely anew doesn't seem to generate the overflow generation data.

Patrick

I stand corrected. I forgot that the repository at hand was connected to another one via objects/info/alternates. If I prune commit-graphs from that alternate, too, then it works alright with your patches.

OK, thanks. That clarifies the situation.

I ordered the patches such that the fix in patch 4 could be immediately testable, which is not the case without patch 3. However, it does leave this temporary state where information can be incorrect if only a subset of the series is applied.

Quoted 16 lines

This makes me wonder how such a bugfix should be handled though. As this series is right now, users will be faced with repository corruption as soon as they upgrade their Git version to one that contains this patch series. This corruption needs manual action: they have to go into the repository, delete the commit-graphs and then optionally create new ones.

This is not a good user experience, and it's worse on the server-side where we now have a timeframe where all commit-graphs are potentially corrupt. This effectively leads to us being unable to serve those repos at all until we have rewritten the commit-graphs because all commands which make use of the commit-graph will now die:

    $ git log
    fatal: commit-graph requires overflow generation data but has none

Quoted 6 lines

So the question is whether this is a change that needs to be rolled out over multiple releases. First we'd get in the bug fix such that we write correct commit-graphs, and after this fix has been released we can also release the fix that starts to actually parse the generation. This ensures there's a grace period during which we can hopefully correct the data on-disk such that users are not faced with failures.

You are right that we need to be careful here, but I also think that previous versions of Git always wrote the correct data. Here is my thought process:

1. To get this bug, we need to have parsed the corrected commit date from an existing commit-graph in order to under-count the number of overflow values.

2. Before this series, Git versions were not parsing the corrected commit date, so they recompute the corrected commit date every time the commit-graph is written, getting the proper count of overflow values.

For these reasons, data written by previous versions of Git are correct and can be trusted without a staged release.

Does this make sense? Or, do you experience a different result when you build commit-graphs with a released Git version and then when writing on top with all patches applied?

Quoted 11 lines

The better alternative would probably be to just gracefully handle commit-graphs which are corrupted in such a way. Can we maybe just continue to not parse generations in case we find that the commit-graph doesn't have overflow generation data?

This is more of a general issue though: commit-graphs are an auxiliary cache that is not required for proper operation at all. If we fail to parse it, then Git shouldn't die but instead fail gracefully just ignore it. Furthermore, if we notice that graphs are corrupt when we try to write new ones, we may just delete the corrupt versions automatically and generate completely new ones.

You are right that we can be better about failures here and report and error instead of a die(). Especially in this case, we could just revert to topological levels instead of throwing out the commit-graph entirely.

This seems like something for another series, so we can be sure to audit all cases of fatal errors when parsing the commit-graph so we catch all of them and do the "best" thing in each case.

Quoted 7 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Quoted 5 lines · Patrick Steinhardt

Quoted 4 lines · Derrick Stolee

Quoted 3 lines · Patrick Steinhardt

Quoted 2 lines · Derrick Stolee

Quoted 1 line · Patrick Steinhardt

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

Quoted 23 lines

Quoted 6 lines

So the question is whether this is a change that needs to be rolled out over multiple releases. First we'd get in the bug fix such that we write correct commit-graphs, and after this fix has been released we can also release the fix that starts to actually parse the generation. This ensures there's a grace period during which we can hopefully correct the data on-disk such that users are not faced with failures.

You are right that we need to be careful here, but I also think that previous versions of Git always wrote the correct data. Here is my thought process:

1. To get this bug, we need to have parsed the corrected commit date from an existing commit-graph in order to under-count the number of overflow values.

2. Before this series, Git versions were not parsing the corrected commit date, so they recompute the corrected commit date every time the commit-graph is written, getting the proper count of overflow values.

For these reasons, data written by previous versions of Git are correct and can be trusted without a staged release.

Quoted 3 lines

Does this make sense? Or, do you experience a different result when you build commit-graphs with a released Git version and then when writing on top with all patches applied?

Just to verify my understanding: you claim that the bug I was hitting shouldn't be encountered in the wild when the release , but only if one were to write a commit-graph with the intermediate stafe until patch 3/4 of your patch series?

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

Quoted 8 lines · Patrick Steinhardt

Quoted 7 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Quoted 5 lines · Patrick Steinhardt

Quoted 4 lines · Derrick Stolee

Quoted 3 lines · Patrick Steinhardt

Quoted 2 lines · Derrick Stolee

Quoted 1 line · Patrick Steinhardt

[1]: https://gitlab.com/gitlab-com/www-gitlab-com.git

...

Quoted 23 lines

Quoted 23 lines

Quoted 6 lines

So the question is whether this is a change that needs to be rolled out over multiple releases. First we'd get in the bug fix such that we write correct commit-graphs, and after this fix has been released we can also release the fix that starts to actually parse the generation. This ensures there's a grace period during which we can hopefully correct the data on-disk such that users are not faced with failures.

You are right that we need to be careful here, but I also think that previous versions of Git always wrote the correct data. Here is my thought process:

1. To get this bug, we need to have parsed the corrected commit date from an existing commit-graph in order to under-count the number of overflow values.

2. Before this series, Git versions were not parsing the corrected commit date, so they recompute the corrected commit date every time the commit-graph is written, getting the proper count of overflow values.

For these reasons, data written by previous versions of Git are correct and can be trusted without a staged release.

Quoted 8 lines

Quoted 3 lines

Does this make sense? Or, do you experience a different result when you build commit-graphs with a released Git version and then when writing on top with all patches applied?

Just to verify my understanding: you claim that the bug I was hitting shouldn't be encountered in the wild when the release , but only if one were to write a commit-graph with the intermediate stafe until patch 3/4 of your patch series?

That is my claim. And my testing of the repo at [1] has demonstrated that it works correctly in these cases.

Quoted 6 lines

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

But I'm not able to generate these warnings from either version. I tried generating different levels of a split commit-graph, but could not reproduce it. If you have reproduction steps using current 'master' (or any released Git version) and the four patches here, then I would love to get a full understanding of your errors.

Thanks,
-Stolee

Quoted 9 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

Quoted 8 lines

But I'm not able to generate these warnings from either version. I tried generating different levels of a split commit-graph, but could not reproduce it. If you have reproduction steps using current 'master' (or any released Git version) and the four patches here, then I would love to get a full understanding of your errors.

Thanks,
-Stolee

I haven't yet been able to reproduce it with publicly available data, but with the internal references I'm able to evoke the warnings reliably. It only works when I have two repositories connected via alternates, when generating the commit-graph in the linked-to repo first, and then generating the commit-graph in the linking repo.

The following recipe allows me to reproduce, but rely on private data:

    $ git --version
    git version 2.35.1

    # The pool repository is the one we're linked to from the fork.
    $ cd "$pool"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ cd "$fork"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ git commit-graph verify --no-progress
    $ echo $?
    0

    # This is 715d08a9e51251ad8290b181b6ac3b9e1f9719d7 with your full v2
    # applied on top.
    $ ~/Development/git/bin-wrappers/git --version
    git version 2.35.1.358.g7ede1bea24

    $ ~/Development/git/bin-wrappers/git commit-graph verify --no-progress
    commit-graph generation for commit 06a91bac00ed11128becd48d5ae77eacd8f24c97 is 1623273624 < 1623273710
    commit-graph generation for commit 0ae91029f27238e8f8e109c6bb3907f864dda14f is 1622151146 < 1622151220
    commit-graph generation for commit 0d4582a33d8c8e3eb01adbf564f5e1deeb3b56a2 is 1631045222 < 1631045225
    commit-graph generation for commit 0daf8976439d7e0bb9710c5ee63b570580e0dc03 is 1620347739 < 1620347789
    commit-graph generation for commit 0e0ee8ffb3fa22cee7d28e21cbd6df26454932cf is 1623783297 < 1623783380
    commit-graph generation for commit 0f08ab3de6ec115ea8a956a1996cb9759e640e74 is 1621543278 < 1621543339
    commit-graph generation for commit 133ed0319b5a66ae0c2be76e5a887b880452b111 is 1620949864 < 1620949915
    commit-graph generation for commit 1341b3e6c63343ae94a8a473fa057126ddd4669a is 1637344364 < 1637344384
    commit-graph generation for commit 15bdfc501c2c9f23e9353bf6e6a5facd9c32a07a is 1623348103 < 1623348133
    ...
    $ echo $?
    1

When generating commit-graphs with your patches applied the verify step works alright.

I've also by accident stumbled over the original error again:

fatal: commit-graph requires overflow generation data but has none

This time it's definitely not caused by generating commit-graphs with an in-between state of your patch series because the data comes straight from production with no changes to the commit-graphs performed by myself. There we're running Git v2.33.1 with a couple of backported patches (see [1]). While those patches cause us to make more use of the commit-graph, none modify the way we generate them.

Of note is that the commit-graph contains references to commits which don't exist in the ODB anymore.

Patrick

[1]: https://gitlab.com/gitlab-org/gitlab-git/-/commits/pks-v2.33.1.gl3

Since our repro relies on private information, but is consistent, I wonder if we should take the patch below, which starts to ignore the older generation number v2 data and only writes freshly-computed numbers.

Clearly, there is something else going on. The situation is not completely understood, but the errors do not reproduce if the commit-graphs are all generated by a Git version including these recent fixes.

If we cannot trust the existing data in the GDAT and GDOV chunks, then we can alter the format to change the chunk IDs for these chunks. This causes the new version of Git to silently ignore the older chunks (and disabling generation number v2 in the process) while writing new commit-graph files with correct data in the GDA2 and GDO2 chunks.

Update commit-graph-format.txt including a historical note about these deprecated chunks.

commit-graph.c +2 -2

index b86a6a634fe..fb2ced0bd6d 100644
@@ -39,8 +39,8 @@ void git_test_write_commit_graph_or_die(void)
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
-#define GRAPH_CHUNKID_GENERATION_DATA 0x47444154 /* "GDAT" */
-#define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f56 /* "GDOV" */
+#define GRAPH_CHUNKID_GENERATION_DATA 0x47444132 /* "GDA2" */
+#define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f32 /* "GDO2" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */

Quoted 4 lines · Derrick Stolee

Since our repro relies on private information, but is consistent, I wonder if we should take the patch below, which starts to ignore the older generation number v2 data and only writes freshly-computed numbers.

;-)

Quoted 4 lines

Clearly, there is something else going on. The situation is not completely understood, but the errors do not reproduce if the commit-graphs are all generated by a Git version including these recent fixes.

Do you mean "we know doing X and then Y and then Z on this particular private data with older version of Git without those two fixes will lead to a broken timestamp, but doing exactly the same with the two fixes, the breakage does not reproduce"? If so, that is quite encouraging news. Thanks for working well together.

Quoted 8 lines

If we cannot trust the existing data in the GDAT and GDOV chunks, then we can alter the format to change the chunk IDs for these chunks. This causes the new version of Git to silently ignore the older chunks (and disabling generation number v2 in the process) while writing new commit-graph files with correct data in the GDA2 and GDO2 chunks.

Update commit-graph-format.txt including a historical note about these deprecated chunks.

Sensible.

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 166

Quoted 12 lines

Documentation/technical/commit-graph-format.txt +8 -0

@@ -156,3 +156,11 @@ CHUNK DATA:
 TRAILER:
 
 	H-byte HASH-checksum of all of the above.
+
+== Historical Notes:
+
+The Generation Data (GDA2) and Generation Data Overflow (GDO2) chunks have
+the number '2' in their chunk IDs because a previous version of Git wrote
+possibly erroneous data in these chunks with the IDs "GDAT" and "GDOV". By
+changing the IDs, newer versions of Git will silently ignore those older
+chunks and write the new information without trusting the incorrect data.

Good. How does a new version of Git skip and ignore GDAT and GDOV in existing files? By not having any code to recognize what they are?

I am wondering if there is some notion of "if you do not understand what this chunk is, you are incapable of handling this file correctly, so do not use it" kind of bit per chunks (similar to the index extensions where ones that begin with [A-Z] are optional) that may negatively affect this plan.

Quoted 5 lines

I am wondering if there is some notion of "if you do not understand what this chunk is, you are incapable of handling this file correctly, so do not use it" kind of bit per chunks (similar to the index extensions where ones that begin with [A-Z] are optional) that may negatively affect this plan.

The chunk IDs do not have this special casing rule. This is a bit unfortunate for certain cases like adding something that _must_ be understood. Here, it works to our benefit that GDAT and GDOV are optional and can be safely ignored. Thus, clients with this patch will ignore GDAT and GDOV and continue using topological levels form the CDAT chunk. Older clients without this patch will ignore the new GDA2 and GDO2 chunks and continue using topological levels.

For Git versions without this topic branch, this "continue using topological levels" means no change of behavior at all.

Quoted 76 lines · Patrick Steinhardt

Quoted 9 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

Quoted 8 lines

But I'm not able to generate these warnings from either version. I tried generating different levels of a split commit-graph, but could not reproduce it. If you have reproduction steps using current 'master' (or any released Git version) and the four patches here, then I would love to get a full understanding of your errors.

Thanks,
-Stolee

I haven't yet been able to reproduce it with publicly available data, but with the internal references I'm able to evoke the warnings reliably. It only works when I have two repositories connected via alternates, when generating the commit-graph in the linked-to repo first, and then generating the commit-graph in the linking repo.

The following recipe allows me to reproduce, but rely on private data:

    $ git --version
    git version 2.35.1

    # The pool repository is the one we're linked to from the fork.
    $ cd "$pool"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ cd "$fork"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ git commit-graph verify --no-progress
    $ echo $?
    0

    # This is 715d08a9e51251ad8290b181b6ac3b9e1f9719d7 with your full v2
    # applied on top.
    $ ~/Development/git/bin-wrappers/git --version
    git version 2.35.1.358.g7ede1bea24

    $ ~/Development/git/bin-wrappers/git commit-graph verify --no-progress
    commit-graph generation for commit 06a91bac00ed11128becd48d5ae77eacd8f24c97 is 1623273624 < 1623273710
    commit-graph generation for commit 0ae91029f27238e8f8e109c6bb3907f864dda14f is 1622151146 < 1622151220
    commit-graph generation for commit 0d4582a33d8c8e3eb01adbf564f5e1deeb3b56a2 is 1631045222 < 1631045225
    commit-graph generation for commit 0daf8976439d7e0bb9710c5ee63b570580e0dc03 is 1620347739 < 1620347789
    commit-graph generation for commit 0e0ee8ffb3fa22cee7d28e21cbd6df26454932cf is 1623783297 < 1623783380
    commit-graph generation for commit 0f08ab3de6ec115ea8a956a1996cb9759e640e74 is 1621543278 < 1621543339
    commit-graph generation for commit 133ed0319b5a66ae0c2be76e5a887b880452b111 is 1620949864 < 1620949915
    commit-graph generation for commit 1341b3e6c63343ae94a8a473fa057126ddd4669a is 1637344364 < 1637344384
    commit-graph generation for commit 15bdfc501c2c9f23e9353bf6e6a5facd9c32a07a is 1623348103 < 1623348133
    ...
    $ echo $?
    1

When generating commit-graphs with your patches applied the verify step works alright.

I've also by accident stumbled over the original error again:

fatal: commit-graph requires overflow generation data but has none

This time it's definitely not caused by generating commit-graphs with an in-between state of your patch series because the data comes straight from production with no changes to the commit-graphs performed by myself. There we're running Git v2.33.1 with a couple of backported patches (see [1]). While those patches cause us to make more use of the commit-graph, none modify the way we generate them.

Quoted 6 lines

Of note is that the commit-graph contains references to commits which don't exist in the ODB anymore.

Patrick

[1]: https://gitlab.com/gitlab-org/gitlab-git/-/commits/pks-v2.33.1.gl3

Thank you for your diligence here, Patrick. I really appreciate the work you're putting in to verify the situation.

Since our repro relies on private information, but is consistent, I wonder if we should take the patch below, which starts to ignore the older generation number v2 data and only writes freshly-computed numbers.

Thanks,
-Stolee

--- 8< ---

From c53d8bd52bbcab3862e8a826ee75692edc7e4173 Mon Sep 17 00:00:00 2001
From: Derrick Stolee <[email protected]>
Date: Wed, 2 Mar 2022 09:45:13 -0500
Subject: [PATCH v3 5/4] commit-graph: declare bankruptcy on GDAT chunks

The Generation Data (GDAT) and Generation Data Overflow (GDOV) chunks store corrected commit date offsets, used for generation number v2. Recent changes have demonstrated that previous versions of Git were incorrectly parsing data from these chunks, but might have also been writing them incorrectly.

I asserted [1] that the previous fixes were sufficient because the known reasons for incorrectly writing generation number v2 data relied on parsing the information incorrectly out of a commit-graph file, but the previous versions of Git were not reading the generation number v2 data.

However, Patrick demonstrated [2] a case where in split commit-graphs across an alternate boundary (and possibly some other special conditions) it was possible to have a commit-graph that was generated by a previous version of Git have incorrect generation number v2 data which results in errors like the following:

commit-graph generation for commit <oid> is 1623273624 < 1623273710

[1] https://lore.kernel.org/git/[email protected]/
[2] https://lore.kernel.org/git/Yh93vOkt2DkrGPh2@ncase/

Clearly, there is something else going on. The situation is not completely understood, but the errors do not reproduce if the commit-graphs are all generated by a Git version including these recent fixes.

If we cannot trust the existing data in the GDAT and GDOV chunks, then we can alter the format to change the chunk IDs for these chunks. This causes the new version of Git to silently ignore the older chunks (and disabling generation number v2 in the process) while writing new commit-graph files with correct data in the GDA2 and GDO2 chunks.

Update commit-graph-format.txt including a historical note about these deprecated chunks.

Reported-by Patrick Steinhardt <[email protected]>

Signed-off-by Derrick Stolee <[email protected]>

---
 Documentation/technical/commit-graph-format.txt | 12 ++++++++++--
 commit-graph.c                                  |  4 ++--
 2 files changed, 12 insertions(+), 4 deletions(-)

Documentation/technical/commit-graph-format.txt +10 -2

index 87971c27dd7..484b185ba98 100644
@@ -93,7 +93,7 @@ CHUNK DATA:
       2 bits of the lowest byte, storing the 33rd and 34th bit of the
       commit time.
 
-  Generation Data (ID: {'G', 'D', 'A', 'T' }) (N * 4 bytes) [Optional]
+  Generation Data (ID: {'G', 'D', 'A', '2' }) (N * 4 bytes) [Optional]
     * This list of 4-byte values store corrected commit date offsets for the
       commits, arranged in the same order as commit data chunk.
     * If the corrected commit date offset cannot be stored within 31 bits,

@@ -104,7 +104,7 @@ CHUNK DATA:
       by compatible versions of Git and in case of split commit-graph chains,
       the topmost layer also has Generation Data chunk.
 
-  Generation Data Overflow (ID: {'G', 'D', 'O', 'V' }) [Optional]
+  Generation Data Overflow (ID: {'G', 'D', 'O', '2' }) [Optional]
     * This list of 8-byte values stores the corrected commit date offsets
       for commits with corrected commit date offsets that cannot be
       stored within 31 bits.

@@ -156,3 +156,11 @@ CHUNK DATA:
 TRAILER:
 
 	H-byte HASH-checksum of all of the above.
+
+== Historical Notes:
+
+The Generation Data (GDA2) and Generation Data Overflow (GDO2) chunks have
+the number '2' in their chunk IDs because a previous version of Git wrote
+possibly erroneous data in these chunks with the IDs "GDAT" and "GDOV". By
+changing the IDs, newer versions of Git will silently ignore those older
+chunks and write the new information without trusting the incorrect data.

commit-graph.c +2 -2

index b86a6a634fe..fb2ced0bd6d 100644
@@ -39,8 +39,8 @@ void git_test_write_commit_graph_or_die(void)
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
-#define GRAPH_CHUNKID_GENERATION_DATA 0x47444154 /* "GDAT" */
-#define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f56 /* "GDOV" */
+#define GRAPH_CHUNKID_GENERATION_DATA 0x47444132 /* "GDA2" */
+#define GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW 0x47444f32 /* "GDO2" */
 #define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
 #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */

Signature · 1 line

2.35.1.138.gfc5de29e9e6

Quoted 92 lines · Derrick Stolee

Quoted 76 lines · Patrick Steinhardt

Quoted 9 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

Quoted 8 lines

But I'm not able to generate these warnings from either version. I tried generating different levels of a split commit-graph, but could not reproduce it. If you have reproduction steps using current 'master' (or any released Git version) and the four patches here, then I would love to get a full understanding of your errors.

Thanks,
-Stolee

I haven't yet been able to reproduce it with publicly available data, but with the internal references I'm able to evoke the warnings reliably. It only works when I have two repositories connected via alternates, when generating the commit-graph in the linked-to repo first, and then generating the commit-graph in the linking repo.

The following recipe allows me to reproduce, but rely on private data:

    $ git --version
    git version 2.35.1

    # The pool repository is the one we're linked to from the fork.
    $ cd "$pool"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ cd "$fork"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ git commit-graph verify --no-progress
    $ echo $?
    0

    # This is 715d08a9e51251ad8290b181b6ac3b9e1f9719d7 with your full v2
    # applied on top.
    $ ~/Development/git/bin-wrappers/git --version
    git version 2.35.1.358.g7ede1bea24

    $ ~/Development/git/bin-wrappers/git commit-graph verify --no-progress
    commit-graph generation for commit 06a91bac00ed11128becd48d5ae77eacd8f24c97 is 1623273624 < 1623273710
    commit-graph generation for commit 0ae91029f27238e8f8e109c6bb3907f864dda14f is 1622151146 < 1622151220
    commit-graph generation for commit 0d4582a33d8c8e3eb01adbf564f5e1deeb3b56a2 is 1631045222 < 1631045225
    commit-graph generation for commit 0daf8976439d7e0bb9710c5ee63b570580e0dc03 is 1620347739 < 1620347789
    commit-graph generation for commit 0e0ee8ffb3fa22cee7d28e21cbd6df26454932cf is 1623783297 < 1623783380
    commit-graph generation for commit 0f08ab3de6ec115ea8a956a1996cb9759e640e74 is 1621543278 < 1621543339
    commit-graph generation for commit 133ed0319b5a66ae0c2be76e5a887b880452b111 is 1620949864 < 1620949915
    commit-graph generation for commit 1341b3e6c63343ae94a8a473fa057126ddd4669a is 1637344364 < 1637344384
    commit-graph generation for commit 15bdfc501c2c9f23e9353bf6e6a5facd9c32a07a is 1623348103 < 1623348133
    ...
    $ echo $?
    1

When generating commit-graphs with your patches applied the verify step works alright.

I've also by accident stumbled over the original error again:

fatal: commit-graph requires overflow generation data but has none

This time it's definitely not caused by generating commit-graphs with an in-between state of your patch series because the data comes straight from production with no changes to the commit-graphs performed by myself. There we're running Git v2.33.1 with a couple of backported patches (see [1]). While those patches cause us to make more use of the commit-graph, none modify the way we generate them.

Quoted 6 lines

Of note is that the commit-graph contains references to commits which don't exist in the ODB anymore.

Patrick

[1]: https://gitlab.com/gitlab-org/gitlab-git/-/commits/pks-v2.33.1.gl3

Thank you for your diligence here, Patrick. I really appreciate the work you're putting in to verify the situation.

Since our repro relies on private information, but is consistent, I wonder if we should take the patch below, which starts to ignore the older generation number v2 data and only writes freshly-computed numbers.

Quoted 2 lines

Thanks,
-Stolee

Thanks. With your patch below the fatal: error is gone, but I'm still seeing the same errors with regards to the commit-graph generations.

So to summarize my findings:

- This bug occurs when writing commit-graphs with v2.35.1, but reading them with your patches.

- This bug occurs when I have two repositories connected via an alternates file. I haven't yet been able to reproduce it in a single repository that is not connected to a separate ODB.

- This bug only occurs when I first generate the commit-graph in the repository I'm borrowing objects from.

- This bug only occurs when I write commit-graphs with --split in both repositories. "Normal" commit-graphs don't have this issue, and neither can I see it with --split=replace or mixed-type commit-graphs.

Beware, the following explanation is based on my very basic understanding of the commit-graph code and thus more likely to be wrong than right:

With the old Git version, we've been mis-parsing the generation because read_generation_data wasn't ever set. As a result it can happen that the second split commit-graph we're generating computes its own generation numbers from the wrong starting point because it uses the mis-parsed generation numbers from the parent commit-graph.

With your patches, we start to correctly account for overflows and would thus end up with a different value for the generation depending on where we parse the commit from: if we parse it from the first commit-graph it would be correct because it's contains the "root" of the generation numbers. But if we parse a commit from the second commit-graph we may have a mismatch because the generation numbers in there may have been derived from generation numbers mis-parsed from the first commit-graph. And because these would be wrong in case there was an overflow it is clear that the new corrected generation number may be wrong, as well.

Quoted 93 lines · Patrick Steinhardt

Quoted 92 lines · Derrick Stolee

Quoted 76 lines · Patrick Steinhardt

Quoted 9 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

Quoted 8 lines

But I'm not able to generate these warnings from either version. I tried generating different levels of a split commit-graph, but could not reproduce it. If you have reproduction steps using current 'master' (or any released Git version) and the four patches here, then I would love to get a full understanding of your errors.

Thanks,
-Stolee

I haven't yet been able to reproduce it with publicly available data, but with the internal references I'm able to evoke the warnings reliably. It only works when I have two repositories connected via alternates, when generating the commit-graph in the linked-to repo first, and then generating the commit-graph in the linking repo.

The following recipe allows me to reproduce, but rely on private data:

    $ git --version
    git version 2.35.1

    # The pool repository is the one we're linked to from the fork.
    $ cd "$pool"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ cd "$fork"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ git commit-graph verify --no-progress
    $ echo $?
    0

    # This is 715d08a9e51251ad8290b181b6ac3b9e1f9719d7 with your full v2
    # applied on top.
    $ ~/Development/git/bin-wrappers/git --version
    git version 2.35.1.358.g7ede1bea24

    $ ~/Development/git/bin-wrappers/git commit-graph verify --no-progress
    commit-graph generation for commit 06a91bac00ed11128becd48d5ae77eacd8f24c97 is 1623273624 < 1623273710
    commit-graph generation for commit 0ae91029f27238e8f8e109c6bb3907f864dda14f is 1622151146 < 1622151220
    commit-graph generation for commit 0d4582a33d8c8e3eb01adbf564f5e1deeb3b56a2 is 1631045222 < 1631045225
    commit-graph generation for commit 0daf8976439d7e0bb9710c5ee63b570580e0dc03 is 1620347739 < 1620347789
    commit-graph generation for commit 0e0ee8ffb3fa22cee7d28e21cbd6df26454932cf is 1623783297 < 1623783380
    commit-graph generation for commit 0f08ab3de6ec115ea8a956a1996cb9759e640e74 is 1621543278 < 1621543339
    commit-graph generation for commit 133ed0319b5a66ae0c2be76e5a887b880452b111 is 1620949864 < 1620949915
    commit-graph generation for commit 1341b3e6c63343ae94a8a473fa057126ddd4669a is 1637344364 < 1637344384
    commit-graph generation for commit 15bdfc501c2c9f23e9353bf6e6a5facd9c32a07a is 1623348103 < 1623348133
    ...
    $ echo $?
    1

When generating commit-graphs with your patches applied the verify step works alright.

I've also by accident stumbled over the original error again:

fatal: commit-graph requires overflow generation data but has none

This time it's definitely not caused by generating commit-graphs with an in-between state of your patch series because the data comes straight from production with no changes to the commit-graphs performed by myself. There we're running Git v2.33.1 with a couple of backported patches (see [1]). While those patches cause us to make more use of the commit-graph, none modify the way we generate them.

Quoted 6 lines

Of note is that the commit-graph contains references to commits which don't exist in the ODB anymore.

Patrick

[1]: https://gitlab.com/gitlab-org/gitlab-git/-/commits/pks-v2.33.1.gl3

Thank you for your diligence here, Patrick. I really appreciate the work you're putting in to verify the situation.

Since our repro relies on private information, but is consistent, I wonder if we should take the patch below, which starts to ignore the older generation number v2 data and only writes freshly-computed numbers.

Quoted 5 lines

Quoted 2 lines

Thanks,
-Stolee

Thanks. With your patch below the fatal: error is gone, but I'm still seeing the same errors with regards to the commit-graph generations.

This is disappointing and unexpected. Thanks for verifying.

Quoted 8 lines

So to summarize my findings:

- This bug occurs when writing commit-graphs with v2.35.1, but reading them with your patches.

- This bug occurs when I have two repositories connected via an alternates file. I haven't yet been able to reproduce it in a single repository that is not connected to a separate ODB.

This is an interesting distinction. One that I didn't think would matter, but I'll look into the code to see how that could affect things.

Quoted 18 lines

- This bug only occurs when I first generate the commit-graph in the repository I'm borrowing objects from.

- This bug only occurs when I write commit-graphs with --split in both repositories. "Normal" commit-graphs don't have this issue, and neither can I see it with --split=replace or mixed-type commit-graphs.

Beware, the following explanation is based on my very basic understanding of the commit-graph code and thus more likely to be wrong than right:

With the old Git version, we've been mis-parsing the generation because read_generation_data wasn't ever set. As a result it can happen that the second split commit-graph we're generating computes its own generation numbers from the wrong starting point because it uses the mis-parsed generation numbers from the parent commit-graph.

Quoted 9 lines

With your patches, we start to correctly account for overflows and would thus end up with a different value for the generation depending on where we parse the commit from: if we parse it from the first commit-graph it would be correct because it's contains the "root" of the generation numbers. But if we parse a commit from the second commit-graph we may have a mismatch because the generation numbers in there may have been derived from generation numbers mis-parsed from the first commit-graph. And because these would be wrong in case there was an overflow it is clear that the new corrected generation number may be wrong, as well.

Hm. My expectation was that the older layers of the split commit-graph would have read_generation_data disabled (because the new Git version cannot read the GDAT chunk) and then the validate_mixed_generation_chain() method would remove read_generation_data from all of the graphs in the list.

Combining this with your thoughts on cross-alternate split commit-graphs, this makes me think we should try this:

--- >8 ---

commit-graph.c +7 -4

index fb2ced0bd6..74c6534f56 100644
@@ -609,8 +609,6 @@ struct commit_graph *read_commit_graph_one(struct repository *r,
 	if (!g)
 		g = load_commit_graph_chain(r, odb);
 
-	validate_mixed_generation_chain(g);
-
 	return g;
 }
 

@@ -668,7 +666,13 @@ static int prepare_commit_graph(struct repository *r)
 	     !r->objects->commit_graph && odb;
 	     odb = odb->next)
 		prepare_commit_graph_one(r, odb);
-	return !!r->objects->commit_graph;
+
+	if (r->objects->commit_graph) {
+		validate_mixed_generation_chain(r->objects->commit_graph);
+		return 1;
+	}
+
+	return 0;
 }
 
 int generation_numbers_enabled(struct repository *r)
 
 
--- >8 ---

Notice that I'm moving the validate_mixed_generation_chain() call out of read_commit_graph_one() and into prepare_commit_graph(). To my understanding, this _should_ have an equivalent end state as the old code, but might be worth trying just as a quick check.

I will continue investigating and try to reproduce with this additional constraint of working across an alternate.

Quoted 186 lines · Derrick Stolee

Quoted 93 lines · Patrick Steinhardt

Quoted 92 lines · Derrick Stolee

Quoted 76 lines · Patrick Steinhardt

Quoted 9 lines · Derrick Stolee

Quoted 6 lines · Patrick Steinhardt

Hum. I have re-verified, and this indeed seems to play out. So I must've accidentally ran all my testing with the state generated without the final patch which fixes the corruption. I do see lots of the following warnings, but overall I can verify and write the commit-graph just fine:

    commit-graph generation for commit c80a42de8803e2d77818d0c82f88e748d7f9425f is 1623362063 < 1623362139

Quoted 8 lines

But I'm not able to generate these warnings from either version. I tried generating different levels of a split commit-graph, but could not reproduce it. If you have reproduction steps using current 'master' (or any released Git version) and the four patches here, then I would love to get a full understanding of your errors.

Thanks,
-Stolee

I haven't yet been able to reproduce it with publicly available data, but with the internal references I'm able to evoke the warnings reliably. It only works when I have two repositories connected via alternates, when generating the commit-graph in the linked-to repo first, and then generating the commit-graph in the linking repo.

The following recipe allows me to reproduce, but rely on private data:

    $ git --version
    git version 2.35.1

    # The pool repository is the one we're linked to from the fork.
    $ cd "$pool"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ cd "$fork"
    $ rm -rf objects/info/commit-graph objects/info/commit-graph
    $ git commit-graph write --split

    $ git commit-graph verify --no-progress
    $ echo $?
    0

    # This is 715d08a9e51251ad8290b181b6ac3b9e1f9719d7 with your full v2
    # applied on top.
    $ ~/Development/git/bin-wrappers/git --version
    git version 2.35.1.358.g7ede1bea24

    $ ~/Development/git/bin-wrappers/git commit-graph verify --no-progress
    commit-graph generation for commit 06a91bac00ed11128becd48d5ae77eacd8f24c97 is 1623273624 < 1623273710
    commit-graph generation for commit 0ae91029f27238e8f8e109c6bb3907f864dda14f is 1622151146 < 1622151220
    commit-graph generation for commit 0d4582a33d8c8e3eb01adbf564f5e1deeb3b56a2 is 1631045222 < 1631045225
    commit-graph generation for commit 0daf8976439d7e0bb9710c5ee63b570580e0dc03 is 1620347739 < 1620347789
    commit-graph generation for commit 0e0ee8ffb3fa22cee7d28e21cbd6df26454932cf is 1623783297 < 1623783380
    commit-graph generation for commit 0f08ab3de6ec115ea8a956a1996cb9759e640e74 is 1621543278 < 1621543339
    commit-graph generation for commit 133ed0319b5a66ae0c2be76e5a887b880452b111 is 1620949864 < 1620949915
    commit-graph generation for commit 1341b3e6c63343ae94a8a473fa057126ddd4669a is 1637344364 < 1637344384
    commit-graph generation for commit 15bdfc501c2c9f23e9353bf6e6a5facd9c32a07a is 1623348103 < 1623348133
    ...
    $ echo $?
    1

When generating commit-graphs with your patches applied the verify step works alright.

I've also by accident stumbled over the original error again:

fatal: commit-graph requires overflow generation data but has none

This time it's definitely not caused by generating commit-graphs with an in-between state of your patch series because the data comes straight from production with no changes to the commit-graphs performed by myself. There we're running Git v2.33.1 with a couple of backported patches (see [1]). While those patches cause us to make more use of the commit-graph, none modify the way we generate them.

Quoted 6 lines

Of note is that the commit-graph contains references to commits which don't exist in the ODB anymore.

Patrick

[1]: https://gitlab.com/gitlab-org/gitlab-git/-/commits/pks-v2.33.1.gl3

Thank you for your diligence here, Patrick. I really appreciate the work you're putting in to verify the situation.

Since our repro relies on private information, but is consistent, I wonder if we should take the patch below, which starts to ignore the older generation number v2 data and only writes freshly-computed numbers.

Quoted 5 lines

Quoted 2 lines

Thanks,
-Stolee

Thanks. With your patch below the fatal: error is gone, but I'm still seeing the same errors with regards to the commit-graph generations.

This is disappointing and unexpected. Thanks for verifying.

Quoted 8 lines

So to summarize my findings:

- This bug occurs when writing commit-graphs with v2.35.1, but reading them with your patches.

- This bug occurs when I have two repositories connected via an alternates file. I haven't yet been able to reproduce it in a single repository that is not connected to a separate ODB.

This is an interesting distinction. One that I didn't think would matter, but I'll look into the code to see how that could affect things.

Quoted 18 lines

- This bug only occurs when I first generate the commit-graph in the repository I'm borrowing objects from.

- This bug only occurs when I write commit-graphs with --split in both repositories. "Normal" commit-graphs don't have this issue, and neither can I see it with --split=replace or mixed-type commit-graphs.

Beware, the following explanation is based on my very basic understanding of the commit-graph code and thus more likely to be wrong than right:

With the old Git version, we've been mis-parsing the generation because read_generation_data wasn't ever set. As a result it can happen that the second split commit-graph we're generating computes its own generation numbers from the wrong starting point because it uses the mis-parsed generation numbers from the parent commit-graph.

Quoted 9 lines

With your patches, we start to correctly account for overflows and would thus end up with a different value for the generation depending on where we parse the commit from: if we parse it from the first commit-graph it would be correct because it's contains the "root" of the generation numbers. But if we parse a commit from the second commit-graph we may have a mismatch because the generation numbers in there may have been derived from generation numbers mis-parsed from the first commit-graph. And because these would be wrong in case there was an overflow it is clear that the new corrected generation number may be wrong, as well.

Hm. My expectation was that the older layers of the split commit-graph would have read_generation_data disabled (because the new Git version cannot read the GDAT chunk) and then the validate_mixed_generation_chain() method would remove read_generation_data from all of the graphs in the list.

Combining this with your thoughts on cross-alternate split commit-graphs, this makes me think we should try this:

--- >8 ---

commit-graph.c +7 -4

index fb2ced0bd6..74c6534f56 100644
@@ -609,8 +609,6 @@ struct commit_graph *read_commit_graph_one(struct repository *r,
 	if (!g)
 		g = load_commit_graph_chain(r, odb);
 
-	validate_mixed_generation_chain(g);
-
 	return g;
 }
 

@@ -668,7 +666,13 @@ static int prepare_commit_graph(struct repository *r)
 	     !r->objects->commit_graph && odb;
 	     odb = odb->next)
 		prepare_commit_graph_one(r, odb);
-	return !!r->objects->commit_graph;
+
+	if (r->objects->commit_graph) {
+		validate_mixed_generation_chain(r->objects->commit_graph);
+		return 1;
+	}
+
+	return 0;
 }
 
 int generation_numbers_enabled(struct repository *r)
 
 
--- >8 ---

Quoted 7 lines

Notice that I'm moving the validate_mixed_generation_chain() call out of read_commit_graph_one() and into prepare_commit_graph(). To my understanding, this _should_ have an equivalent end state as the old code, but might be worth trying just as a quick check.

I will continue investigating and try to reproduce with this additional constraint of working across an alternate.

My attempts to reproduce this across an alternate have failed. I tried running the following test against Git without these patches, then verify with the newer version of Git. (I also have generated a few new layers on top with these patches, and they correctly drop the GDA2 and GDO2 chunks when the lower layers "don't have gen v2".)

test_description='commit-graph with offsets across alternates' . ./test-lib.sh

if ! test_have_prereq TIME_IS_64BIT || ! test_have_prereq TIME_T_IS_64BIT then
skip_all='skipping 64-bit timestamp tests'
test_done
fi

UNIX_EPOCH_ZERO="@0 +0000"
FUTURE_DATE="@4147483646 +0000"

GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0

test_expect_success 'generate alternate split commit-graph' '

	git init alternate &&
	(
		cd alternate &&
		test_commit --date "$UNIX_EPOCH_ZERO" 1 &&
		test_commit --date "$FUTURE_DATE" 2 &&
		git commit-graph write --reachable &&
		test_commit --date "$UNIX_EPOCH_ZERO" 3 &&
		test_commit --date "$FUTURE_DATE" 4 &&
		git commit-graph write --reachable --split=no-merge
	) &&
	git clone --shared alternate fork &&
	(
		cd fork &&
		test_commit --date "$UNIX_EPOCH_ZERO" 5 &&
		test_commit --date "$FUTURE_DATE" 6 &&
		git commit-graph write --reachable --split=no-merge &&
		test_commit --date "$UNIX_EPOCH_ZERO" 7 &&
		test_commit --date "$FUTURE_DATE" 8 &&
		git commit-graph write --reachable --split=no-merge
	)

'

test_done

My testing after running this with -d allows me to reliably see these layers being created with GDAT and GDOV chunks. Running the 'git commit-graph verify' command with the new code does not show those errors, even after adding commits and another layer to the split commit-graph.

I look forward to any additional insights you might have here.

Quoted 1 line · Derrick Stolee

On 3/3/2022 11:00 AM, Derrick Stolee wrote:

Quoted 57 lines

Quoted 2 lines

I will continue investigating and try to reproduce with this additional constraint of working across an alternate.

My attempts to reproduce this across an alternate have failed. I tried running the following test against Git without these patches, then verify with the newer version of Git. (I also have generated a few new layers on top with these patches, and they correctly drop the GDA2 and GDO2 chunks when the lower layers "don't have gen v2".)

test_description='commit-graph with offsets across alternates' . ./test-lib.sh

if ! test_have_prereq TIME_IS_64BIT || ! test_have_prereq TIME_T_IS_64BIT then
skip_all='skipping 64-bit timestamp tests'
test_done
fi

UNIX_EPOCH_ZERO="@0 +0000"
FUTURE_DATE="@4147483646 +0000"

GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0

test_expect_success 'generate alternate split commit-graph' '

	git init alternate &&
	(
		cd alternate &&
		test_commit --date "$UNIX_EPOCH_ZERO" 1 &&
		test_commit --date "$FUTURE_DATE" 2 &&
		git commit-graph write --reachable &&
		test_commit --date "$UNIX_EPOCH_ZERO" 3 &&
		test_commit --date "$FUTURE_DATE" 4 &&
		git commit-graph write --reachable --split=no-merge
	) &&
	git clone --shared alternate fork &&
	(
		cd fork &&
		test_commit --date "$UNIX_EPOCH_ZERO" 5 &&
		test_commit --date "$FUTURE_DATE" 6 &&
		git commit-graph write --reachable --split=no-merge &&
		test_commit --date "$UNIX_EPOCH_ZERO" 7 &&
		test_commit --date "$FUTURE_DATE" 8 &&
		git commit-graph write --reachable --split=no-merge
	)

'

test_done

My testing after running this with -d allows me to reliably see these layers being created with GDAT and GDOV chunks. Running the 'git commit-graph verify' command with the new code does not show those errors, even after adding commits and another layer to the split commit-graph.

Quoted 1 line

I look forward to any additional insights you might have here.

I don't really know why, but now I've become unable to reproduce it again. I think we should just go with your patch 5/4 on top -- it does fix the most important issue, which is the die() I saw on almost all commands. The second part about the warnings I'm just not sure about, but I don't think it should stop this patch series given my own uncertainty.

Thanks for following up. I agree that with 5/4 we should be safe.

I'll remain available to quickly respond if anything else surprising comes up in this area.

Quoted 2 lines · Patrick Steinhardt

Quoted 1 line · Derrick Stolee

On 3/3/2022 11:00 AM, Derrick Stolee wrote:

...

Quoted 57 lines

Quoted 57 lines

Quoted 2 lines

I will continue investigating and try to reproduce with this additional constraint of working across an alternate.

My attempts to reproduce this across an alternate have failed. I tried running the following test against Git without these patches, then verify with the newer version of Git. (I also have generated a few new layers on top with these patches, and they correctly drop the GDA2 and GDO2 chunks when the lower layers "don't have gen v2".)

test_description='commit-graph with offsets across alternates' . ./test-lib.sh

if ! test_have_prereq TIME_IS_64BIT || ! test_have_prereq TIME_T_IS_64BIT then
skip_all='skipping 64-bit timestamp tests'
test_done
fi

UNIX_EPOCH_ZERO="@0 +0000"
FUTURE_DATE="@4147483646 +0000"

GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0

test_expect_success 'generate alternate split commit-graph' '

	git init alternate &&
	(
		cd alternate &&
		test_commit --date "$UNIX_EPOCH_ZERO" 1 &&
		test_commit --date "$FUTURE_DATE" 2 &&
		git commit-graph write --reachable &&
		test_commit --date "$UNIX_EPOCH_ZERO" 3 &&
		test_commit --date "$FUTURE_DATE" 4 &&
		git commit-graph write --reachable --split=no-merge
	) &&
	git clone --shared alternate fork &&
	(
		cd fork &&
		test_commit --date "$UNIX_EPOCH_ZERO" 5 &&
		test_commit --date "$FUTURE_DATE" 6 &&
		git commit-graph write --reachable --split=no-merge &&
		test_commit --date "$UNIX_EPOCH_ZERO" 7 &&
		test_commit --date "$FUTURE_DATE" 8 &&
		git commit-graph write --reachable --split=no-merge
	)

'

test_done

My testing after running this with -d allows me to reliably see these layers being created with GDAT and GDOV chunks. Running the 'git commit-graph verify' command with the new code does not show those errors, even after adding commits and another layer to the split commit-graph.

Quoted 8 lines

Quoted 1 line

I look forward to any additional insights you might have here.

I don't really know why, but now I've become unable to reproduce it again. I think we should just go with your patch 5/4 on top -- it does fix the most important issue, which is the die() I saw on almost all commands. The second part about the warnings I'm just not sure about, but I don't think it should stop this patch series given my own uncertainty.

Thanks for following up. I agree that with 5/4 we should be safe.

I'll remain available to quickly respond if anything else surprising comes up in this area.

Thanks!
-Stolee

Quoted 72 lines · Derrick Stolee

Quoted 2 lines · Patrick Steinhardt

Quoted 1 line · Derrick Stolee

On 3/3/2022 11:00 AM, Derrick Stolee wrote:

...

Quoted 57 lines

Quoted 57 lines

Quoted 2 lines

I will continue investigating and try to reproduce with this additional constraint of working across an alternate.

My attempts to reproduce this across an alternate have failed. I tried running the following test against Git without these patches, then verify with the newer version of Git. (I also have generated a few new layers on top with these patches, and they correctly drop the GDA2 and GDO2 chunks when the lower layers "don't have gen v2".)

test_description='commit-graph with offsets across alternates' . ./test-lib.sh

if ! test_have_prereq TIME_IS_64BIT || ! test_have_prereq TIME_T_IS_64BIT then
skip_all='skipping 64-bit timestamp tests'
test_done
fi

UNIX_EPOCH_ZERO="@0 +0000"
FUTURE_DATE="@4147483646 +0000"

GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=0

test_expect_success 'generate alternate split commit-graph' '

	git init alternate &&
	(
		cd alternate &&
		test_commit --date "$UNIX_EPOCH_ZERO" 1 &&
		test_commit --date "$FUTURE_DATE" 2 &&
		git commit-graph write --reachable &&
		test_commit --date "$UNIX_EPOCH_ZERO" 3 &&
		test_commit --date "$FUTURE_DATE" 4 &&
		git commit-graph write --reachable --split=no-merge
	) &&
	git clone --shared alternate fork &&
	(
		cd fork &&
		test_commit --date "$UNIX_EPOCH_ZERO" 5 &&
		test_commit --date "$FUTURE_DATE" 6 &&
		git commit-graph write --reachable --split=no-merge &&
		test_commit --date "$UNIX_EPOCH_ZERO" 7 &&
		test_commit --date "$FUTURE_DATE" 8 &&
		git commit-graph write --reachable --split=no-merge
	)

'

test_done

My testing after running this with -d allows me to reliably see these layers being created with GDAT and GDOV chunks. Running the 'git commit-graph verify' command with the new code does not show those errors, even after adding commits and another layer to the split commit-graph.

Quoted 8 lines

Quoted 1 line

I look forward to any additional insights you might have here.

I don't really know why, but now I've become unable to reproduce it again. I think we should just go with your patch 5/4 on top -- it does fix the most important issue, which is the die() I saw on almost all commands. The second part about the warnings I'm just not sure about, but I don't think it should stop this patch series given my own uncertainty.

Thanks for following up. I agree that with 5/4 we should be safe.

Quoted 5 lines

I'll remain available to quickly respond if anything else surprising comes up in this area.

Thanks!
-Stolee

There is another surprise I hit today in the context of generation numbers. In production, I found the following bug:

signal: aborted (core dumped): BUG: chunk-format.c:88: expected to write 8 bytes to chunk 47444f56, but wrote 168304 instead

47444f56 is the GENERATION_DATA_OVERFLOW chunk ID, and seemingly the precomputed size we intended to write was mismatching the data we have actually been writing to disk. And I think this stems from a mismatch in how we precompute the number of generation data overflows compared to how we're actually writing the data to disk:

t/t5318-commit-graph.sh +2 -0

index 1afee1c2705..5e4b0216fa6 100755
@@ -815,6 +815,19 @@ test_expect_success 'corrupt commit-graph write (missing tree)' '
 	)
 '
 
+# The remaining tests check timestamps that flow over
+# 32-bits. The graph_git_behavior checks can't take a

t/t5318-commit-graph.sh +4 -0

@@ -867,4 +880,8 @@ test_expect_success 'set up and verify repo with generation data overflow chunk'
 
 graph_git_behavior 'generation data overflow chunk repo' repo left right
 
+# Do not add tests at the end of this file, unless they require 64-bit
+# timestamps, since this portion of the script is only executed when
+# time data types have 64 bits.
+
 test_done

commit-graph.c static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, · line 809

Quoted 2 lines · Derrick Stolee via GitGitGadget

commit-graph.c +1 -1

-			graph_data->generation = get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
+			graph_data->generation = item->date + get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);

Wow, that's embarrassing.

Quoted 10 lines

t/t5318-commit-graph.sh +2 -0

index 1afee1c2705..5e4b0216fa6 100755
@@ -815,6 +815,19 @@ test_expect_success 'corrupt commit-graph write (missing tree)' '
 	)
 '
 
+# The remaining tests check timestamps that flow over
+# 32-bits. The graph_git_behavior checks can't take a

t/t5318-commit-graph.sh test_expect_success 'corrupt commit-graph write (missing tree)' ' · line 829

Quoted 10 lines

t/t5318-commit-graph.sh +10 -0

+# prereq, so just stop here if we are on a 32-bit machine.
+
+if ! test_have_prereq TIME_IS_64BIT
+then
+	test_done
+fi
+if ! test_have_prereq TIME_T_IS_64BIT
+then
+	test_done
+fi

The above is OK but is there a reason why we cannot do

	if A || B
	then
		test_done
	fi

here (I am assuming not, but in case I am missing the reason why it has to be separate)?

Quoted 4 lines

t/t5318-commit-graph.sh +0 -0

@@ -832,10 +845,10 @@ test_expect_success 'corrupt commit-graph write (missing tree)' '
 # The largest offset observed is 2 ^ 31, just large enough to overflow.
 #
 

t/t5318-commit-graph.sh test_expect_success 'corrupt commit-graph write (missing tree)' ' · line 851

Quoted 6 lines

t/t5318-commit-graph.sh +2 -2

-test_expect_success 'set up and verify repo with generation data overflow chunk' '
+test_expect_success TIME_IS_64BIT,TIME_T_IS_64BIT 'set up and verify repo with generation data overflow chunk' '
 	objdir=".git/objects" &&
 	UNIX_EPOCH_ZERO="@0 +0000" &&
-	FUTURE_DATE="@2147483646 +0000" &&
+	FUTURE_DATE="@4000000000 +0000" &&

OK. 16#EE6B2800 too large to fit and will cause wrapping around with signed 32-bit integer.

Quoted 20 lines

t/t5318-commit-graph.sh test_expect_success 'corrupt commit-graph write (missing tree)' ' · line 829

Quoted 12 lines

t/t5318-commit-graph.sh +12 -0

+# The remaining tests check timestamps that flow over
+# 32-bits. The graph_git_behavior checks can't take a
+# prereq, so just stop here if we are on a 32-bit machine.
+
+if ! test_have_prereq TIME_IS_64BIT
+then
+	test_done
+fi
+if ! test_have_prereq TIME_T_IS_64BIT
+then
+	test_done
+fi

The above is OK but is there a reason why we cannot do

	if A || B
	then
		test_done
	fi

Quoted 2 lines

here (I am assuming not, but in case I am missing the reason why it has to be separate)?

Does not need to be separate. I just discovered the two different prereqs for similar, but not exact, checks. I can swap this to an or statement.

From: Derrick Stolee <[email protected]>

The corrected commit date was first documented in 5a3b130ca (doc: add corrected commit date info, 2021-01-16) and it used an optional chunk to augment the commit-graph format without modifying the file format version.

One major benefit to this approach is that corrected commit dates could be written without causing a backwards compatibility issue with Git versions that do not understand them. The topological level was still available in the CDAT chunk as it was before.

However, this causes a different issue: more data needs to be loaded from disk when parsing commits from the commit-graph. In cases where there is no significant algorithmic gain from using corrected commit dates, commit walks take up to 20% longer because of this extra data.

Create a new file format version for the commit-graph format that differs only in the CDAT chunk: it now stores corrected commit date offsets. This brings our data back to normal and will demonstrate performance gains in almost all cases.

The corrected commit date was first documented in 5a3b130ca (doc: add corrected commit date info, 2021-01-16) and it used an optional chunk to augment the commit-graph format without modifying the file format version.

One major benefit to this approach is that corrected commit dates could be written without causing a backwards compatibility issue with Git versions that do not understand them. The topological level was still available in the CDAT chunk as it was before.

However, this causes a different issue: more data needs to be loaded from disk when parsing commits from the commit-graph. In cases where there is no significant algorithmic gain from using corrected commit dates, commit walks take up to 20% longer because of this extra data.

Create a new file format version for the commit-graph format that differs only in the CDAT chunk: it now stores corrected commit date offsets. This brings our data back to normal and will demonstrate performance gains in almost all cases.

Signed-off-by Derrick Stolee <[email protected]>

---
 .../technical/commit-graph-format.txt         | 22 ++++++++++++++-----
 1 file changed, 17 insertions(+), 5 deletions(-)

Documentation/technical/commit-graph-format.txt +14 -5

index 87971c27dd7..2cb48993314 100644
@@ -36,7 +36,7 @@ HEADER:
       The signature is: {'C', 'G', 'P', 'H'}
 
   1-byte version number:
-      Currently, the only valid version is 1.
+      This version number can be 1 or 2.
 
   1-byte Hash Version
       We infer the hash length (H) from this value:

@@ -85,13 +85,22 @@ CHUNK DATA:
       position. If there are more than two parents, the second value
       has its most-significant bit on and the other bits store an array
       position into the Extra Edge List chunk.
-    * The next 8 bytes store the topological level (generation number v1)
-      of the commit and
-      the commit time in seconds since EPOCH. The generation number
-      uses the higher 30 bits of the first 4 bytes, while the commit
+    * The next 8 bytes store the generation number information of the
+      commit and the commit time in seconds since EPOCH. The generation
+      number uses the higher 30 bits of the first 4 bytes, while the commit
       time uses the 32 bits of the second 4 bytes, along with the lowest
       2 bits of the lowest byte, storing the 33rd and 34th bit of the
       commit time.
+      - If the commit-graph file format is version 1, then the higher 30
+	bits contain the topological level (generation number v1) for the
+	commit.
+      - If the commit-graph file format is version 2, then the higher 30
+	bits contain the corrected commit date offset (generation number
+	v2) for the commit, except if the offset cannot be stored within
+	29 bits. If the offset is too large for 29 bits, then the value
+	stored here has its most-significant bit on and the other bits
+	store the position of the corrected commit date in the Generation
+	Date Overflow chunk.
 
   Generation Data (ID: {'G', 'D', 'A', 'T' }) (N * 4 bytes) [Optional]
     * This list of 4-byte values store corrected commit date offsets for the

On Thu, Feb 24 2022, Derrick Stolee via GitGitGadget wrote:

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 120

Quoted 12 lines

Generation Data (ID: {'G', 'D', 'A', 'T' }) (N * 4 bytes) [Optional]
* This list of 4-byte values store corrected commit date offsets for the

Documentation/technical/commit-graph-format.txt +3 -0

@@ -103,6 +112,9 @@ CHUNK DATA:
     * Generation Data chunk is present only when commit-graph file is written
       by compatible versions of Git and in case of split commit-graph chains,
       the topmost layer also has Generation Data chunk.
+    * This chunk does not exist if the commit-graph file format version is 2,
+      because the corrected commit date offset data is stored in the Commit
+      Data chunk.
 
   Generation Data Overflow (ID: {'G', 'D', 'O', 'V' }) [Optional]
     * This list of 8-byte values stores the corrected commit date offsets

We talked a while ago now about how we do commit-graph format changes and this is partially echoing those earlier questions[1] from 2019.

I fully understand why we're writing this amended CDAT chunk in a different layout. By not having the GDAT side-chunk to look up in the data is more local, that part of the file is more compact etc.

What I don't understand is why getting those performance improvements requires the breaking version change & the writing of the incompatible version number.

I.e. couldn't the differently formatted CDAT chunk be written instead to a new chunk name (say "2DAT") instead? Per [1] we'd pay a small fixed cost for a possibly empty chunk (I didn't re-do those numbers), but surely the performance improvements will be about the same for that miniscule overhead.

It will give you something you can't have here, which is optional compatibility with older clients by writing both versions. That'll be a ~2x as large file on disk, but with the page cache & each client version skipping to the data it needs caching characteristics & data locality should work out to about the same thing.

Or maybe they won't. I just found it surprising when reviewing this to not find an answer to why that approach wasn't
considered.

Quoted 3 lines · Ævar Arnfjörð Bjarmason

On Thu, Feb 24 2022, Derrick Stolee via GitGitGadget wrote:

...

Quoted 24 lines

Documentation/technical/commit-graph-format.txt CHUNK DATA: · line 120

Quoted 12 lines

Generation Data (ID: {'G', 'D', 'A', 'T' }) (N * 4 bytes) [Optional]
* This list of 4-byte values store corrected commit date offsets for the

Documentation/technical/commit-graph-format.txt +3 -0

@@ -103,6 +112,9 @@ CHUNK DATA:
     * Generation Data chunk is present only when commit-graph file is written
       by compatible versions of Git and in case of split commit-graph chains,
       the topmost layer also has Generation Data chunk.
+    * This chunk does not exist if the commit-graph file format version is 2,
+      because the corrected commit date offset data is stored in the Commit
+      Data chunk.
 
   Generation Data Overflow (ID: {'G', 'D', 'O', 'V' }) [Optional]
     * This list of 8-byte values stores the corrected commit date offsets

We talked a while ago now about how we do commit-graph format changes and this is partially echoing those earlier questions[1] from 2019.

I fully understand why we're writing this amended CDAT chunk in a different layout. By not having the GDAT side-chunk to look up in the data is more local, that part of the file is more compact etc.

What I don't understand is why getting those performance improvements requires the breaking version change & the writing of the incompatible version number.

Quoted 5 lines

I.e. couldn't the differently formatted CDAT chunk be written instead to a new chunk name (say "2DAT") instead? Per [1] we'd pay a small fixed cost for a possibly empty chunk (I didn't re-do those numbers), but surely the performance improvements will be about the same for that miniscule overhead.

CDAT is a required chunk. It is part of the v1 spec that CDAT exists and is correct. All other Git clients will error out when reading a "v1" graph without such a chunk, and in a way that is less helpful to users. Instead of clearly indicating "file version is too new" it will say "commit-graph is missing the Commit Data chunk" which is not helpful.

Quoted 5 lines

It will give you something you can't have here, which is optional compatibility with older clients by writing both versions. That'll be a ~2x as large file on disk, but with the page cache & each client version skipping to the data it needs caching characteristics & data locality should work out to about the same thing.

Writing both is the only way that this could work without incrementing the graph version number, but I'd rather just update the number and avoid wasting the effort to write that extra data.

It seems you are hyper-focused on "we don't _need_ to update the version number" and you are willing to recommend wasteful approaches in order to support that stance.

So: you're right. We don't _need_ to update the version number. But this is the best choice among the options available.

Quoted 3 lines

Or maybe they won't. I just found it surprising when reviewing this to not find an answer to why that approach wasn't
considered.

The point is to create a new format that can be chosen when deployed in an environment where older Git versions will not exist (such as a Git server). The new version is not chosen by default and instead is opt-in through the commitGraph.generationVersion config option.

Perhaps in a year or two we would consider making this the new default, but there is no rush to do so.

Quoted 6 lines · Derrick Stolee

Quoted 3 lines · Ævar Arnfjörð Bjarmason

Or maybe they won't. I just found it surprising when reviewing this to not find an answer to why that approach wasn't
considered.

Quoted 7 lines

The point is to create a new format that can be chosen when deployed in an environment where older Git versions will not exist (such as a Git server). The new version is not chosen by default and instead is opt-in through the commitGraph.generationVersion config option.

Perhaps in a year or two we would consider making this the new default, but there is no rush to do so.

Looking into this a bit more I think that in either case this is less of a big deal after my 43d35618055 (commit-graph write: don't die if the existing graph is corrupt, 2019-03-25), which came out of some of those discussions at the time of [1].

I.e. now a client that only understands version N-1 will warn when loading it, wheras it's only if a pre-v2.22.0 client (which has that commit) reads the repository that we'd hard die on it, correct?

But speaking of hyper-focus. I think that arguably applies to you in this case when considering the trade-offs of these sorts of format changes :)

I.e. you're primarily considering cases of say a git server (presumably running on GitHub) or another such deployment where it's easy to have full control over all of your versions "in the wild".

And thus a three-phase rollout of something like a format change can be done in a timely and predictable manner.

But git is used by *a lot* of people in a bunch of different scenarios. E.g.:

* A shared (hopefully read-only) NFS mounted by remote "unmanaged" clients.
* A tarred-up directory including a .git, which may be transferred to a machine with a pre-v2.22.0 version.

Or even softer cases of failure, such as:

* A cronjob causes an alert/incident somewhere because the server operator started writing a new version, but forgot about a set of machines that are still on the old version.

I think that even if it's less conceptually clean it's worth considering being over backwards to be kinder to such use-cases, unless it's really required for other reasons to break such in-the-wild use-cases.

Or in this case, if it's thought to be worth it to help reviewers decide by separating the performance improvement aspect from the changed interaction between new graphs and older clients.

As a further nit on the proposed end-state here: Do I understand it correctly that commitGraph.generationVersion=[1|2] (i.e. on current "master") will always result in a file that's compatible with older versions, since the only thing "v2" there controls now is to write the optional GDAT and GDOV chunks?

Whereas going from commitGraph.generationVersion=2 to commitGraph.generationVersion=3 in this series will impact older clients as noted above, since we're bumping the version (of the file, to 2 if the config is 3, which as Junio noted is a bit confusing).

I think if you're set on going down the path of bumping the top-level version that deserves to be made much clearer in the added documentation. Right now the only hint to that is a passing mention that for v3:

[it] will be incompatible with some old versions of Git

Which if we're opting for breaking format changes really should note some of the caveats above, that pre-v2.22.0 hard-dies, and probably describe "some old versions of Git" a bit more clearly.

It actually means once this gets released "the git version that was the latest one you could download yesterday". Which a reader of the docs probably won't expect when starting to play with this in mixed-version environment.

1. https://lore.kernel.org/git/[email protected]/

Quoted 30 lines · Ævar Arnfjörð Bjarmason

Quoted 6 lines · Derrick Stolee

Quoted 3 lines · Ævar Arnfjörð Bjarmason

Or maybe they won't. I just found it surprising when reviewing this to not find an answer to why that approach wasn't
considered.

Quoted 7 lines

The point is to create a new format that can be chosen when deployed in an environment where older Git versions will not exist (such as a Git server). The new version is not chosen by default and instead is opt-in through the commitGraph.generationVersion config option.

Perhaps in a year or two we would consider making this the new default, but there is no rush to do so.

Looking into this a bit more I think that in either case this is less of a big deal after my 43d35618055 (commit-graph write: don't die if the existing graph is corrupt, 2019-03-25), which came out of some of those discussions at the time of [1].

I.e. now a client that only understands version N-1 will warn when loading it, wheras it's only if a pre-v2.22.0 client (which has that commit) reads the repository that we'd hard die on it, correct?

But speaking of hyper-focus. I think that arguably applies to you in this case when considering the trade-offs of these sorts of format changes :)

Quoted 3 lines

I.e. you're primarily considering cases of say a git server (presumably running on GitHub) or another such deployment where it's easy to have full control over all of your versions "in the wild".

I'm thinking of servers, yes, but also 99% of clients who only upgrade (or _maybe_ downgrade to a recent, previous version occasionally).

Quoted 10 lines

And thus a three-phase rollout of something like a format change can be done in a timely and predictable manner.

But git is used by *a lot* of people in a bunch of different scenarios. E.g.:

* A shared (hopefully read-only) NFS mounted by remote "unmanaged" clients.
* A tarred-up directory including a .git, which may be transferred to a machine with a pre-v2.22.0 version.

Quoted 5 lines

Or even softer cases of failure, such as:

* A cronjob causes an alert/incident somewhere because the server operator started writing a new version, but forgot about a set of machines that are still on the old version.

It is important to continue supporting these cases, and this change does not cause any issues for them.

However, this handful of corner cases should not block progress in the main cases.

Quoted 30 lines

I think that even if it's less conceptually clean it's worth considering being over backwards to be kinder to such use-cases, unless it's really required for other reasons to break such in-the-wild use-cases.

Or in this case, if it's thought to be worth it to help reviewers decide by separating the performance improvement aspect from the changed interaction between new graphs and older clients.

As a further nit on the proposed end-state here: Do I understand it correctly that commitGraph.generationVersion=[1|2] (i.e. on current "master") will always result in a file that's compatible with older versions, since the only thing "v2" there controls now is to write the optional GDAT and GDOV chunks?

Whereas going from commitGraph.generationVersion=2 to commitGraph.generationVersion=3 in this series will impact older clients as noted above, since we're bumping the version (of the file, to 2 if the config is 3, which as Junio noted is a bit confusing).

I think if you're set on going down the path of bumping the top-level version that deserves to be made much clearer in the added documentation. Right now the only hint to that is a passing mention that for v3:

[it] will be incompatible with some old versions of Git

Which if we're opting for breaking format changes really should note some of the caveats above, that pre-v2.22.0 hard-dies, and probably describe "some old versions of Git" a bit more clearly.

Quoted 6 lines

It actually means once this gets released "the git version that was the latest one you could download yesterday". Which a reader of the docs probably won't expect when starting to play with this in mixed-version environment.

1. https://lore.kernel.org/git/[email protected]/

This documentation could be altered to be specific about versions, but such a specific change makes assumptions of the version that will include it. As of now, the generation number v2 fixes will _probably_ get in for 2.36 and the format change would have enough time to cook for 2.37, so I'll update the docs to refer to that version explicitly.

The pre-2.22.0 change might be helpful to mention, but it could also be noise to the reader. We can revisit this when these patches are submitted again in another thread. There's also concern about third- party tools like libgit2. I'd rather draw the line as "tread carefully here" than "here is so much information that a reader might think it is all they need to know".

Quoted 31 lines · Derrick Stolee

Quoted 30 lines · Ævar Arnfjörð Bjarmason

Quoted 6 lines · Derrick Stolee

Quoted 3 lines · Ævar Arnfjörð Bjarmason

Or maybe they won't. I just found it surprising when reviewing this to not find an answer to why that approach wasn't
considered.

Quoted 7 lines

The point is to create a new format that can be chosen when deployed in an environment where older Git versions will not exist (such as a Git server). The new version is not chosen by default and instead is opt-in through the commitGraph.generationVersion config option.

Perhaps in a year or two we would consider making this the new default, but there is no rush to do so.

Looking into this a bit more I think that in either case this is less of a big deal after my 43d35618055 (commit-graph write: don't die if the existing graph is corrupt, 2019-03-25), which came out of some of those discussions at the time of [1].

I.e. now a client that only understands version N-1 will warn when loading it, wheras it's only if a pre-v2.22.0 client (which has that commit) reads the repository that we'd hard die on it, correct?

But speaking of hyper-focus. I think that arguably applies to you in this case when considering the trade-offs of these sorts of format changes :)

Quoted 6 lines

Quoted 3 lines

I.e. you're primarily considering cases of say a git server (presumably running on GitHub) or another such deployment where it's easy to have full control over all of your versions "in the wild".

I'm thinking of servers, yes, but also 99% of clients who only upgrade (or _maybe_ downgrade to a recent, previous version occasionally).

*nod*

Quoted 16 lines

Quoted 15 lines

And thus a three-phase rollout of something like a format change can be done in a timely and predictable manner.

But git is used by *a lot* of people in a bunch of different scenarios. E.g.:

* A shared (hopefully read-only) NFS mounted by remote "unmanaged" clients.
* A tarred-up directory including a .git, which may be transferred to a machine with a pre-v2.22.0 version.

Or even softer cases of failure, such as:

* A cronjob causes an alert/incident somewhere because the server operator started writing a new version, but forgot about a set of machines that are still on the old version.

Quoted 2 lines

It is important to continue supporting these cases, and this change does not cause any issues for them.

The issues in those cases will range from warnings on older versions when loading the graph to errors if it's pre-v2.22.0, with the performance benefits v3 placing them out of range of v2-only clients.

I think arguable that's OK/worth it, but it's "not [any] issues", no?

Quoted 2 lines

However, this handful of corner cases should not block progress in the main cases.

What progress would be blocked?

I'm only talking about whether we choose to consider a "new graph" to be an:

<existing version number>
<existing chunk name (old content, possibly empty)> <new chunk name (new content)>

v.s.:

<old/new version number>
<existing chunk name old/new (incompatible) content>

I.e. the "progress" this series is about is in getting the data locality with smaller data with the new content.

But that's also possible to get with a very low amount of fixed-overhead.

Per the referenced E-Mail an "empty" commit-graph file was ~1k bytes in 2019, I haven't re-checked. In terms of wasted space it's miniscule & <1/4 of one FS page on Linux.

I'm not just trying to rehash the same points, I *think* the version bump is just an aesthetic choice & we're not getting any performance difference out of that.

But I'm not sure from the "block progress" etc., so maybe I'm still missing something...

Quoted 42 lines

Quoted 30 lines

I think that even if it's less conceptually clean it's worth considering being over backwards to be kinder to such use-cases, unless it's really required for other reasons to break such in-the-wild use-cases.

Or in this case, if it's thought to be worth it to help reviewers decide by separating the performance improvement aspect from the changed interaction between new graphs and older clients.

As a further nit on the proposed end-state here: Do I understand it correctly that commitGraph.generationVersion=[1|2] (i.e. on current "master") will always result in a file that's compatible with older versions, since the only thing "v2" there controls now is to write the optional GDAT and GDOV chunks?

Whereas going from commitGraph.generationVersion=2 to commitGraph.generationVersion=3 in this series will impact older clients as noted above, since we're bumping the version (of the file, to 2 if the config is 3, which as Junio noted is a bit confusing).

I think if you're set on going down the path of bumping the top-level version that deserves to be made much clearer in the added documentation. Right now the only hint to that is a passing mention that for v3:

[it] will be incompatible with some old versions of Git

Which if we're opting for breaking format changes really should note some of the caveats above, that pre-v2.22.0 hard-dies, and probably describe "some old versions of Git" a bit more clearly.

Quoted 6 lines

It actually means once this gets released "the git version that was the latest one you could download yesterday". Which a reader of the docs probably won't expect when starting to play with this in mixed-version environment.

1. https://lore.kernel.org/git/[email protected]/

This documentation could be altered to be specific about versions, but such a specific change makes assumptions of the version that will include it. As of now, the generation number v2 fixes will _probably_ get in for 2.36 and the format change would have enough time to cook for 2.37, so I'll update the docs to refer to that version explicitly.

...

Quoted 6 lines

The pre-2.22.0 change might be helpful to mention, but it could also be noise to the reader. We can revisit this when these patches are submitted again in another thread. There's also concern about third- party tools like libgit2. I'd rather draw the line as "tread carefully here" than "here is so much information that a reader might think it is all they need to know".

In terms of concern about libgit2 or any other implementation (which I haven't looked at) isn't "tread carefully" to do it with new chunks if possible, which we've done before with BIDX/BDAT, v.s. a version bump we haven't done?

I'd think it wouldn't be an issue either way for any reader of the format, and libgit2 is more specialized & won't have someone on RHEL6 or whatever trying to inspect a random repo.

It just seems like a win-win to have a performance improvement with smooth backwards compatibility v.s. without, if that's possible.

Quoted 66 lines · Ævar Arnfjörð Bjarmason

Quoted 31 lines · Derrick Stolee

Quoted 30 lines · Ævar Arnfjörð Bjarmason

Quoted 6 lines · Derrick Stolee

Quoted 3 lines · Ævar Arnfjörð Bjarmason

Or maybe they won't. I just found it surprising when reviewing this to not find an answer to why that approach wasn't
considered.

Quoted 7 lines

The point is to create a new format that can be chosen when deployed in an environment where older Git versions will not exist (such as a Git server). The new version is not chosen by default and instead is opt-in through the commitGraph.generationVersion config option.

Perhaps in a year or two we would consider making this the new default, but there is no rush to do so.

Looking into this a bit more I think that in either case this is less of a big deal after my 43d35618055 (commit-graph write: don't die if the existing graph is corrupt, 2019-03-25), which came out of some of those discussions at the time of [1].

I.e. now a client that only understands version N-1 will warn when loading it, wheras it's only if a pre-v2.22.0 client (which has that commit) reads the repository that we'd hard die on it, correct?

But speaking of hyper-focus. I think that arguably applies to you in this case when considering the trade-offs of these sorts of format changes :)

Quoted 6 lines

Quoted 3 lines

I.e. you're primarily considering cases of say a git server (presumably running on GitHub) or another such deployment where it's easy to have full control over all of your versions "in the wild".

I'm thinking of servers, yes, but also 99% of clients who only upgrade (or _maybe_ downgrade to a recent, previous version occasionally).

*nod*

Quoted 10 lines

Quoted 10 lines

And thus a three-phase rollout of something like a format change can be done in a timely and predictable manner.

But git is used by *a lot* of people in a bunch of different scenarios. E.g.:

* A shared (hopefully read-only) NFS mounted by remote "unmanaged" clients.
* A tarred-up directory including a .git, which may be transferred to a machine with a pre-v2.22.0 version.

Quoted 8 lines

Quoted 5 lines

Or even softer cases of failure, such as:

* A cronjob causes an alert/incident somewhere because the server operator started writing a new version, but forgot about a set of machines that are still on the old version.

It is important to continue supporting these cases, and this change does not cause any issues for them.

The issues in those cases will range from warnings on older versions when loading the graph to errors if it's pre-v2.22.0, with the performance benefits v3 placing them out of range of v2-only clients.

Quoted 1 line

I think arguable that's OK/worth it, but it's "not [any] issues", no?

What I mean is that this change does not enable the new graph version by default, so these users do not have any issues unless someone opts in to the feature while in this mixed scenario.

Quoted 16 lines

Quoted 2 lines

However, this handful of corner cases should not block progress in the main cases.

What progress would be blocked?

I'm only talking about whether we choose to consider a "new graph" to be an:

<existing version number>
<existing chunk name (old content, possibly empty)> <new chunk name (new content)>

v.s.:

<old/new version number>
<existing chunk name old/new (incompatible) content>

Quoted 8 lines

I.e. the "progress" this series is about is in getting the data locality with smaller data with the new content.

But that's also possible to get with a very low amount of fixed-overhead.

Per the referenced E-Mail an "empty" commit-graph file was ~1k bytes in 2019, I haven't re-checked. In terms of wasted space it's miniscule & <1/4 of one FS page on Linux.

If you're talking "empty" data, then you need to have an empty Commit Data chunk _and_ and empty OID Lookup chunk in order to not have breakage. So you'd need duplicate versions of these chunks for the new "Commit Data 2" chunk. Then we need special-casing for all of this during parsing that is unnecessary complexity.

Finally, the end result becomes "older versions get slower without any warning" instead of "older versions get a message about not understanding the commit-graph file".

Quoted 6 lines

I'm not just trying to rehash the same points, I *think* the version bump is just an aesthetic choice & we're not getting any performance difference out of that.

But I'm not sure from the "block progress" etc., so maybe I'm still missing something...

The fact that we have a Generation Data chunk instead of already bumping the file format version number is already a concession to this concern about backwards compatibility.

With the point above about empty Commit Data Chunks, the only way to properly conserve backwards compatibility is to have a full Commit Data Chunk as well as a second copy that contains the new offsets instead of topological levels. This is wasteful.

Quoted 52 lines

Quoted 42 lines

Quoted 30 lines

I think that even if it's less conceptually clean it's worth considering being over backwards to be kinder to such use-cases, unless it's really required for other reasons to break such in-the-wild use-cases.

Or in this case, if it's thought to be worth it to help reviewers decide by separating the performance improvement aspect from the changed interaction between new graphs and older clients.

As a further nit on the proposed end-state here: Do I understand it correctly that commitGraph.generationVersion=[1|2] (i.e. on current "master") will always result in a file that's compatible with older versions, since the only thing "v2" there controls now is to write the optional GDAT and GDOV chunks?

Whereas going from commitGraph.generationVersion=2 to commitGraph.generationVersion=3 in this series will impact older clients as noted above, since we're bumping the version (of the file, to 2 if the config is 3, which as Junio noted is a bit confusing).

I think if you're set on going down the path of bumping the top-level version that deserves to be made much clearer in the added documentation. Right now the only hint to that is a passing mention that for v3:

[it] will be incompatible with some old versions of Git

Which if we're opting for breaking format changes really should note some of the caveats above, that pre-v2.22.0 hard-dies, and probably describe "some old versions of Git" a bit more clearly.

Quoted 6 lines

It actually means once this gets released "the git version that was the latest one you could download yesterday". Which a reader of the docs probably won't expect when starting to play with this in mixed-version environment.

1. https://lore.kernel.org/git/[email protected]/

This documentation could be altered to be specific about versions, but such a specific change makes assumptions of the version that will include it. As of now, the generation number v2 fixes will _probably_ get in for 2.36 and the format change would have enough time to cook for 2.37, so I'll update the docs to refer to that version explicitly.

...

Quoted 6 lines

The pre-2.22.0 change might be helpful to mention, but it could also be noise to the reader. We can revisit this when these patches are submitted again in another thread. There's also concern about third- party tools like libgit2. I'd rather draw the line as "tread carefully here" than "here is so much information that a reader might think it is all they need to know".

Quoted 4 lines

In terms of concern about libgit2 or any other implementation (which I haven't looked at) isn't "tread carefully" to do it with new chunks if possible, which we've done before with BIDX/BDAT, v.s. a version bump we haven't done?

New chunks adding new information is part of the design. Changing the location of existing data is new here.

Quoted 6 lines

I'd think it wouldn't be an issue either way for any reader of the format, and libgit2 is more specialized & won't have someone on RHEL6 or whatever trying to inspect a random repo.

It just seems like a win-win to have a performance improvement with smooth backwards compatibility v.s. without, if that's possible.

You are right that it is _possible_, but I don't think that the side-effects are worth it. Those being:

* "Empty CDAT Chunk": Silently slowing down older clients.
* "Duplicate CDAT Chunk": Wasted data.

Finally, I want to reiterate that by making this opt-in, users make the call about whether or not they are in a scenario where this compatibility issue is appropriate for them. This includes waiting to see if third-party tools like libgit2 are updated to understand this version.

Quoted 9 lines · Ævar Arnfjörð Bjarmason

Quoted 3 lines · Derrick Stolee

I think arguable that's OK/worth it, but it's "not [any] issues", no?

What I mean is that this change does not enable the new graph version by default, so these users do not have any issues unless someone opts in to the feature while in this mixed scenario.

Indeed. FWIW I wasn't confused about that bit. I'm just commenting on /how/ we do version upgrades, and if we can save users unnecessary hassle relatively easily.

But I also think the writing is on the wall that you'll want to (understandably) bump the default sooner than later, or if not for this data for other future chunks.

Quoted 3 lines

Finally, the end result becomes "older versions get slower without any warning" instead of "older versions get a message about not understanding the commit-graph file".

Sure, IF you want to write such an empty chunk. The point is that you now have the option.

And this is the same edge case we already dealt with for GDAT/GDOV. I.e. older readers who didn't understand it would be slower.

We can still have a feature to make older clients intentionally break/warn, it seems to me that if you'd want such a thing you'd want it aside from the specific mechanism of this proposed upgrade.

Or you could dual-write the data for older clients, which I think probably isn't worth the hassle.

I.e. if you're worried about silent slowdown older clients happily ignoring the BIDX and BDAT chunks are silently slower.

From: Derrick Stolee <[email protected]>

The commit-graph file format v2 alters how it stores the corrected commit date offsets within the Commit Data chunk instead of a separate chunk. The idea is to significantly reduce the amount of data loaded from disk while parsing the commit-graph.

We need to alter the error message when we see a file format version outside of our range now that multiple are possible. This has a non-functional side-effect of altering a use of GRAPH_VERSION within write_commit_graph().

By storing the file format version in 'struct commit_graph', we can alter the parsing code to depend on that version value. This involves changing where we look for the corrected commit date offset, but also which constants we use for jumping into the Generation Data Overflow chunk. The Commit Data chunk only has 30 bits available for the offset while the Generation Data chunk has 32 bits. This only makes a meaningful difference in very malformed repositories.

Also, we need to be careful about how we enable using corrected commit dates and generation numbers to rely upon the read_generation_data value instead of a non-zero value in the Commit Date chunk. In generation_numbers_enabled(), the first_generation variable is attemptint to look for the first topological level stored to see that it is nonzero. However, for a v2 commit-graph, this value is actually likely to be zero because the corrected commit date offset is probably zero.

Quoted 20 lines · Derrick Stolee via GitGitGadget

From: Derrick Stolee <[email protected]>

The commit-graph file format v2 alters how it stores the corrected commit date offsets within the Commit Data chunk instead of a separate chunk. The idea is to significantly reduce the amount of data loaded from disk while parsing the commit-graph.

We need to alter the error message when we see a file format version outside of our range now that multiple are possible. This has a non-functional side-effect of altering a use of GRAPH_VERSION within write_commit_graph().

By storing the file format version in 'struct commit_graph', we can alter the parsing code to depend on that version value. This involves changing where we look for the corrected commit date offset, but also which constants we use for jumping into the Generation Data Overflow chunk. The Commit Data chunk only has 30 bits available for the offset while the Generation Data chunk has 32 bits. This only makes a meaningful difference in very malformed repositories.

Quoted 8 lines

Also, we need to be careful about how we enable using corrected commit dates and generation numbers to rely upon the read_generation_data value instead of a non-zero value in the Commit Date chunk. In generation_numbers_enabled(), the first_generation variable is attemptint to look for the first topological level stored to see that it is nonzero. However, for a v2 commit-graph, this value is actually likely to be zero because the corrected commit date offset is probably zero.

I see references to OVERFLOW_V3 that comes after OVERFLOW, but there is no OVERFLOW_V2. Intended, or should it be V2 to match the "file format v2" of "generation number v2"? It is getting awkward to have two different version scheme ("gen v2" means corrected committer timestamp, whose on-disk representation is different between "file v1" and "file v2", and this OVERFLOW vs OVERFLOW_V3 is about the difference between "file v1" and "file v2" if I am following the series correctly).

This patch series includes two distinct, but similarly-motivated parts:

* Patches 1-4 fix some bugs in the commit-graph generation number v2.
* Patches 5-7 add a new generation number v3 by incrementing the commit-graph file format.

I had been thinking about generation number v3, which is the same corrected commit date as generation number v2, but it is stored in the Commit Data chunk, requiring a new commit-graph file format version. This breaks compatibility with older versions of Git, so it requires opt-in via the commitGraph.generationVersion config value. The only improvement over version 2 is that the commit-graph file is smaller, so I/O time is reduced.

However, while exploring this idea I found bugs in generation number v2. In particular, Git has been ignoring them since shortly after they were introduced. This is due to a bug I introduced when trying to make split commit-graphs safer with mixed generation number versions. I also noticed an issue with the offset overflows that I only noticed after writing generation number v3 using a smaller offset size, actually triggering the bug in the test suite.

I'm submitting these two things together so we can see them all at once, but I'd be happy to split this into two series. The first four patches are important bug fixes, so we can consider them as higher-priority.

Thanks, -Stolee

Quoted 5 lines

I'm submitting these two things together so we can see them all at once, but I'd be happy to split this into two series. The first four patches are important bug fixes, so we can consider them as higher-priority.

Thanks, -Stolee

Thanks, will take a look.

Quoted 4 lines · Junio C Hamano

Quoted 4 lines

I'm submitting these two things together so we can see them all at once, but I'd be happy to split this into two series. The first four patches are important bug fixes, so we can consider them as higher-priority.

Quoted 3 lines

Quoted 1 line

Thanks, -Stolee

Thanks, will take a look.

Overall it was a pleasant read, even though my reading hiccupped in a few places. It does look like two separate topics, one of which builds on the other.

From: Derrick Stolee <[email protected]>

It can be helpful to verify that the 'struct commit_graph' that results from parsing a commit-graph is correctly structured. The existence of different chunks is not enough to verify that all of the optional features are correctly enabled.

Update 'test-tool read-graph' to output an "options:" line that includes information for different parts of the struct commit_graph.

In particular, this change demonstrates that the read_generation_data option is never being enabled, which will be fixed in a later change.

Signed-off-by Derrick Stolee <[email protected]>

---
 t/helper/test-read-graph.c    | 13 +++++++++++++
 t/t4216-log-bloom.sh          |  1 +
 t/t5318-commit-graph.sh       |  1 +
 t/t5324-split-commit-graph.sh |  5 +++++
 4 files changed, 20 insertions(+)

t/helper/test-read-graph.c +1 -0

index 75927b2c81d..c3b6b8d1734 100644
@@ -3,6 +3,7 @@
 #include "commit-graph.h"
 #include "repository.h"
 #include "object-store.h"
+#include "bloom.h"
 
 int cmd__read_graph(int argc, const char **argv)
 {

t/helper/test-read-graph.c +9 -0

+		       graph->bloom_filter_settings->hash_version,
+		       graph->bloom_filter_settings->bits_per_entry,
+		       graph->bloom_filter_settings->num_hashes);
+	if (graph->read_generation_data)
+		printf(" read_generation_data");
+	if (graph->topo_levels)
+		printf(" topo_levels");
+	printf("\n");
+
 	UNLEAK(graph);
 
 	return 0;

t/t4216-log-bloom.sh +1 -0

index cc3cebf6722..5ed6d2a21c1 100755
@@ -48,6 +48,7 @@ graph_read_expect () {
 	header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0
 	num_commits: $1
 	chunks: oid_fanout oid_lookup commit_metadata generation_data bloom_indexes bloom_data
+	options: bloom(1,10,7)
 	EOF
 	test-tool read-graph >actual &&
 	test_cmp expect actual

t/t5318-commit-graph.sh +1 -0

index edb728f77c3..2b05026cf6d 100755
@@ -104,6 +104,7 @@ graph_read_expect() {
 	header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0
 	num_commits: $1
 	chunks: oid_fanout oid_lookup commit_metadata$OPTIONAL
+	options:
 	EOF
 	test-tool read-graph >output &&
 	test_cmp expect output

t/t5324-split-commit-graph.sh +4 -0

index 847b8097109..778fa418de2 100755
@@ -34,6 +34,7 @@ graph_read_expect() {
 	header: 43475048 1 $(test_oid oid_version) 4 $NUM_BASE
 	num_commits: $1
 	chunks: oid_fanout oid_lookup commit_metadata generation_data
+	options:
 	EOF
 	test-tool read-graph >output &&
 	test_cmp expect output

@@ -508,6 +509,7 @@ test_expect_success 'setup repo for mixed generation commit-graph-chain' '
 		header: 43475048 1 $(test_oid oid_version) 4 1
 		num_commits: $NUM_SECOND_LAYER_COMMITS
 		chunks: oid_fanout oid_lookup commit_metadata
+		options:
 		EOF
 		test_cmp expect output &&
 		git commit-graph verify &&

@@ -540,6 +542,7 @@ test_expect_success 'do not write generation data chunk if not present on existi
 		header: 43475048 1 $(test_oid oid_version) 4 2
 		num_commits: $NUM_THIRD_LAYER_COMMITS
 		chunks: oid_fanout oid_lookup commit_metadata
+		options:
 		EOF
 		test_cmp expect output &&
 		git commit-graph verify

@@ -581,6 +584,7 @@ test_expect_success 'do not write generation data chunk if the topmost remaining
 		header: 43475048 1 $(test_oid oid_version) 4 2
 		num_commits: $(($NUM_THIRD_LAYER_COMMITS + $NUM_FOURTH_LAYER_COMMITS))
 		chunks: oid_fanout oid_lookup commit_metadata
+		options:
 		EOF
 		test_cmp expect output &&
 		git commit-graph verify

From: Derrick Stolee <[email protected]>
[...]

commit-graph.c +7 -3

index 265c010122e..a19bd96c2ee 100644
@@ -1556,12 +1556,16 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 				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++;
 			}
 		}
 	}
+
+	for (i = 0; i < ctx->commits.nr; i++) {
+		struct commit *c = ctx->commits.list[i];
+		timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
+		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
+			ctx->num_generation_data_overflows++;
+	}
 	stop_progress(&ctx->progress);
 }
 

t/t5318-commit-graph.sh +0 -0

index 2b05026cf6d..f9bffe38013 100755
@@ -467,10 +467,10 @@ test_expect_success 'warn on improper hash version' '
 	)
 '

NUM_COMMITS=9

t/t5324-split-commit-graph.sh +4 -0

index 778fa418de2..669ddc645fa 100755
@@ -30,11 +30,16 @@ graph_read_expect() {
 	then
 		NUM_BASE=$2
 	fi
+	OPTIONS=
+	if test -z "$3"
+	then
+		OPTIONS=" read_generation_data"

t/t5318-commit-graph.sh graph_read_expect() { · line 104

Quoted 4 lines · Derrick Stolee via GitGitGadget

From: Derrick Stolee <[email protected]>
[...]

t/t5318-commit-graph.sh +2 -0

+	GENERATION_VERSION=2
+	if test ! -z "$3"

TIL this works somewhere :)

I thought it *might* be unportable behavior (but didn't check at first), but it's not! We have a few such cases already.

But IMO much less puzzling would be at least:

    if ! test -z "$3"

Or in this case, more plainly:

    if test -n "$3"

t/t5318-commit-graph.sh graph_read_expect() { · line 112

Quoted 8 lines

t/t5318-commit-graph.sh +8 -0

+	then
+		GENERATION_VERSION=$3
+	fi
+	OPTIONS=
+	if test $GENERATION_VERSION -gt 1
+	then
+		OPTIONS=" read_generation_data"
+	fi

Or actually, since we don't use $GENERATION_VERSION further down setting it to a default etc. here seems a bit odd. Perhaps something closer to:

    if test $# -eq 3 && test $3 -gt 1

It's also possible to be more clever as e.g.:

    test "${3:-2}" -gt 1

But that hardly seems worth it...

Quoted 19 lines

NUM_COMMITS=9

t/t5324-split-commit-graph.sh +5 -1

index 778fa418de2..669ddc645fa 100755
@@ -30,11 +30,16 @@ graph_read_expect() {
 	then
 		NUM_BASE=$2
 	fi
+	OPTIONS=
+	if test -z "$3"
+	then
+		OPTIONS=" read_generation_data"
+	fi
 	cat >expect <<- EOF
 	header: 43475048 1 $(test_oid oid_version) 4 $NUM_BASE
 	num_commits: $1
 	chunks: oid_fanout oid_lookup commit_metadata generation_data
-	options:

t/t5324-split-commit-graph.sh graph_read_expect() { · line 45

Quoted 4 lines

t/t5324-split-commit-graph.sh +1 -0

+	options:$OPTIONS
 	EOF
 	test-tool read-graph >output &&
 	test_cmp expect output

Not a new issue, but it would be nice to have the mostly copy/pasted code in a lib-commit-graph.sh or something, but probably too distracting for this small series...

From: Derrick Stolee <[email protected]>

The Generation Data Chunk was implemented and tested in e8b63005c (commit-graph: implement generation data chunk, 2021-01-16), but the test was carefully constructed to work on systems with 32-bit dates. Since the corrected commit date offsets still required more than 31 bits, this triggered writing the generation_data_overflow chunk.

However, upon closer look, the write_graph_chunk_generation_data_overflow() method writes the offsets to the chunk (as dictated by the format) but fill_commit_graph_info() treats the value in the chunk as if it is the full corrected commit date (not an offset). For some reason, this does not cause an issue when using the FUTURE_DATE specified in t5318-commit-graph.sh, but it does show up as a failure in 'git commit-graph verify' if we increase that FUTURE_DATE to be above four billion.

Fix this error and update the test to require 64-bit dates so we can safely use this large value in our test.

commit-graph.c +1 -1

index 8e52bb09552..b86a6a634fe 100644
@@ -806,7 +806,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 				die(_("commit-graph requires overflow generation data but has none"));
 
 			offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
-			graph_data->generation = get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
+			graph_data->generation = item->date + get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
 		} else
 			graph_data->generation = item->date + offset;
 	} else

t/t5318-commit-graph.sh +0 -0

index 1afee1c2705..f4ffaad661d 100755

In particular, Git has been ignoring corrected commit dates since shortly after they were introduced. This is due to a bug I introduced when trying to make split commit-graphs safer with mixed generation number versions. I also noticed an issue with the offset overflows that I only noticed after writing generation number v3 using a smaller offset size, actually triggering the bug in the test suite.

From: Derrick Stolee <[email protected]>

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. This causes an under-count in the number of overflow values.

It is incorrect to add an increment to num_generation_data_overflows next to this 'continue' statement, 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.

Create a new t5328-commit-graph-64-bit-time.sh test script to handle special cases of testing 64-bit timestampes. This helps demonstrate this bug in more cases. It still won't hit all potential cases until the next change, which reenables reading generation numbers. Use the skip_all trick from 0a2bfccb9c8 (t0051: use "skip_all" under !MINGW in single-test file, 2022-02-04) to make the output clean when run on a 32-bit system.

Hepled-by Ævar Arnfjörð Bjarmason <[email protected]>

Quoted 9 lines

Create a new t5328-commit-graph-64-bit-time.sh test script to handle special cases of testing 64-bit timestampes. This helps demonstrate this bug in more cases. It still won't hit all potential cases until the next change, which reenables reading generation numbers. Use the skip_all trick from 0a2bfccb9c8 (t0051: use "skip_all" under !MINGW in single-test file, 2022-02-04) to make the output clean when run on a 32-bit system.

Hepled-by Ævar Arnfjörð Bjarmason <[email protected]>

I can typofix this one locally if needed.

Quoted 8 lines · Junio C Hamano

Quoted 8 lines

Create a new t5328-commit-graph-64-bit-time.sh test script to handle special cases of testing 64-bit timestampes. This helps demonstrate this bug in more cases. It still won't hit all potential cases until the next change, which reenables reading generation numbers. Use the skip_all trick from 0a2bfccb9c8 (t0051: use "skip_all" under !MINGW in single-test file, 2022-02-04) to make the output clean when run on a 32-bit system.

Quoted 3 lines

Quoted 1 line

Hepled-by Ævar Arnfjörð Bjarmason <[email protected]>

I can typofix this one locally if needed.

What I meant was s/timestampes/timestamps/ and s/Hepled/Helped/.