Implement Corrected Commit Date

Hi Abhishek,

All right.

All right.

I see that you went with proposed more complex (but better) solution...

A simpler solution would be to create a new merged layer without GDAT if any of the layers being merged do not have GDAT.

In this solution merging 3+4+5, 3+4, and even 2+3 would result with layer without GDAT, and only merging 1+2 would result in layer with GDAT.

All right.

[...]

OK.

All right.

[...]

Actually I am not against fixing the whitespace in the neighbourhood of changes, so you can keep it or revert it (discard).

Thanks.

Best,
--
Jakub Narębski

From: Abhishek Kumar <[email protected]>

With corrected commit dates implemented, we no longer have to rely on commit date as a heuristic in paint_down_to_common().

t6024-recursive-merge setups a unique repository where all commits have the same committer date without well-defined merge-base. As this has already caused problems (as noted in 859fdc0 (commit-graph: define GIT_TEST_COMMIT_GRAPH, 2018-08-29)), we disable commit graph within the test script.

---
 commit-graph.c             | 14 ++++++++++++++
 commit-graph.h             |  6 ++++++
 commit-reach.c             |  2 +-
 t/t6024-recursive-merge.sh |  4 +++-
 4 files changed, 24 insertions(+), 2 deletions(-)

index c1292f8e08..6411068411 100644
@@ -703,6 +703,20 @@ int generation_numbers_enabled(struct repository *r)
 	return !!first_generation;
 }
 
+int corrected_commit_dates_enabled(struct repository *r)
+{
+	struct commit_graph *g;
+	if (!prepare_commit_graph(r))
+		return 0;
+
+	g = r->objects->commit_graph;
+
+	if (!g->num_commits)
+		return 0;
+
+	return !!g->chunk_generation_data;
+}
+
 static void close_commit_graph_one(struct commit_graph *g)
 {
 	if (!g)

index 3cf89d895d..e22ec1e626 100644
@@ -91,6 +91,12 @@ struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size);
  */
 int generation_numbers_enabled(struct repository *r);
 
+/*
+ * Return 1 if and only if the repository has a commit-graph
+ * file and generation data chunk has been written for the file.
+ */
+int corrected_commit_dates_enabled(struct repository *r);
+
 enum commit_graph_write_flags {
 	COMMIT_GRAPH_WRITE_APPEND     = (1 << 0),
 	COMMIT_GRAPH_WRITE_PROGRESS   = (1 << 1),

index 470bc80139..3a1b925274 100644
@@ -39,7 +39,7 @@ static struct commit_list *paint_down_to_common(struct repository *r,
 	int i;
 	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 
-	if (!min_generation)
+	if (!min_generation && !corrected_commit_dates_enabled(r))
 		queue.compare = compare_commits_by_commit_date;
 
 	one->object.flags |= PARENT1;

index 332cfc53fd..d3def66e7d 100755
@@ -15,6 +15,8 @@ GIT_COMMITTER_DATE="2006-12-12 23:28:00 +0100"
 export GIT_COMMITTER_DATE
 
 test_expect_success 'setup tests' '
+	GIT_TEST_COMMIT_GRAPH=0 &&
+	export GIT_TEST_COMMIT_GRAPH &&
 	echo 1 >a1 &&
 	git add a1 &&
 	GIT_AUTHOR_DATE="2006-12-12 23:00:00" git commit -m 1 a1 &&

@@ -66,7 +68,7 @@ test_expect_success 'setup tests' '
 '
 
 test_expect_success 'combined merge conflicts' '
-	test_must_fail env GIT_TEST_COMMIT_GRAPH=0 git merge -m final G
+	test_must_fail git merge -m final G
 '
 
 test_expect_success 'result contains a conflict' '

gitgitgadget

Hello Abhishek,

All right, but it would be nice to have some benchmark data: what were performance when using topological levels, what was performance when using commit date heuristics (before this patch), what is performace now when using corrected commit date.

OK?

I have reorderd files for easier review.

      v2.18.0: 0.122s    167,468 walked
  v2.19.0-rc1: 0.547s    635,579 walked
         HEAD: 0.127s

Jakub Narębski

In hindsight, that is a terrible explanation. Here's what I have revised this to:

With corrected commit dates implemented, we no longer have to rely on commit date as a heuristic in paint_down_to_common().

While using corrected commit dates Git walks nearly the same number of commits as commit date, the process is slower as for each comparision we have to access the commit-slab (for corrected committer date) instead of accessing struct member (for committer date).

For example, the command git merge-base v4.8 v4.9 on the linux repository walks 167468 commits, taking 0.135s for committer date and 167496 commits, taking 0.157s for corrected committer date respectively.

t6404-recursive-merge setups a unique repository where all commits have the same committer date without well-defined merge-base. As this has already caused problems (as noted in 859fdc0 (commit-graph: define GIT_TEST_COMMIT_GRAPH, 2018-08-29)).

While running tests with GIT_TEST_COMMIT_GRAPH unset, we use committer date as a heuristic in paint_down_to_common(). 6404.1 'combined merge conflicts' merges commits in the order:
- Merge C with B to form a intermediate commit.
- Merge the intermediate commit with A.

With GIT_TEST_COMMIT_GRAPH=1, we write a commit-graph and subsequently use the corrected committer date, which changes the order in which commits are merged:
- Merge A with B to form a intermediate commit.
- Merge the intermediate commit with C.

While resulting repositories are equivalent, 6404.4 'virtual trees were processed' fails with GIT_TEST_COMMIT_GRAPH=1 as we are selecting different merge-bases and thus have different object ids for the intermediate commits.

As this has already causes problems (as noted in 859fdc0 (commit-graph:
define GIT_TEST_COMMIT_GRAPH, 2018-08-29)), we disable commit graph within t6404-recursive-merge.

The previous commit didn't need to walk the whole split commit-graph chain. Because of how we are handling writing in a mixed generation data chunk, if a layer has generation data chunk, all layers below it have a generation data chunk as well.

So, there are two cases at hand:

- Topmost layer has generation data chunk, so we know all layers below it has generation data chunk and we can read values from it.
- Topmost layer does not have generation data chunk, so we know we can't read from generation data chunk.

Just checking the topmost layer suffices - modified the previous commit.

Then, this function is more or less the same as g->read_generation_data that is, if we are reading from generation data chunk, we are using corrected commit dates.

Mentioned in the commit message - we walk (nearly) the same number of commits but take somewhat longer.

With the explanation in commit message, it's clear to see how using corrected commit dates leads to an (incorrectly) failing test. Does it still make sense to seperate them?

Thanks
- Abhishek

Hello,

All right, the new proposed commit message has this benchmark data. Thanks.

Much better. Thanks a lot.

[...]

Errr... but validate_mixed_generation_chain() introduced in previous commit in this patch series *does* walk all the layers of the whole split commit-graph chain.

	static void validate_mixed_generation_chain(struct repository *r)
	{
		struct commit_graph *g = r->objects->commit_graph;
		int read_generation_data = 1;
	
		while (g) {
			if (!g->chunk_generation_data) {
				read_generation_data = 0;
				break;
			}
			g = g->base_graph;
		}
	
		g = r->objects->commit_graph;
	
		while (g) {
			g->read_generation_data = read_generation_data;
			g = g->base_graph;
		}
	}

Moreover it "marks up" the whole chain, actually walking it twice.

You wrote somewhere else (possibly after I wrote this post) that this was needed to handle git commit-graph validate, if I remember it correctly.

If it is true, then we need both approaches: the less expensive one (relying on our assumptions) and the more expensive one. But we need to better explain both: why we need more expensive one, why we can use the less expensive onne (how we ensure that the requirements are fulfilled).

All right. That explains how corrected_commit_dates_enabled() works, but not why we need also validate_mixed_generation_chain() that sets g->read_generation_data for every layer in the chain.

All right, the new proposed commit message has it.

Sidenote: this is outside of the scope of this patch series, but perhaps we should think about bringing the generation field from the commit-slab back as a member of the struct commit; this would need profiling and benchmarking of the typical workload to get amortized performance across many git commands.

Note: this might be now t/t6404-recursive-merge.sh -- 6404 ot 6024.

No, I think that the new commit message explains why those changes are together.

On the other hand it might be a good idea to add a TODO comment to this test to mark it as fragile (fixing it is certainly out of scope of this patch series, but better have something to remind us about the issue). Perhaps:

# TODO: fragile test, relies on specific resolving of ambiguity

Or something like that. The original commit that added GIT_TEST_COMMIT_GRAPH=0 (for a single test) explained:

There is one test in t6024-recursive-merge.sh that relies on the merge-base algorithm picking one of two ambiguous merge-bases, and the commit-graph feature changes which merge-base is picked.

I'm not sure of we could salvage some of this test as it is now adding env GIT_TEST_COMMIT_GRAPH=0 in more individual tests instead of turning it off for the whole test script. But that is something that we can do later.

Best,

Jakub Narębski

From: Abhishek Kumar <[email protected]>

With generation data chunk and corrected commit dates implemented, let's update the technical documentation for commit-graph.

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

index 440541045d..71c43884ec 100644
@@ -4,11 +4,7 @@ Git commit graph format
 The Git commit graph stores a list of commit OIDs and some associated
 metadata, including:
 
-- The generation number of the commit. Commits with no parents have
-  generation number 1; commits with parents have generation number
-  one more than the maximum generation number of its parents. We
-  reserve zero as special, and can be used to mark a generation
-  number invalid or as "not computed".
+- The generation number of the commit.
 
 - The root tree OID.
 

@@ -88,6 +84,12 @@ 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]
+    * This list of 4-byte values store corrected commit date offsets for the
+      commits, arranged in the same order as commit data chunk.
+    * This list can be later modified to store future generation number related
+      data.
+
   Extra Edge List (ID: {'E', 'D', 'G', 'E'}) [Optional]
       This list of 4-byte values store the second through nth parents for
       all octopus merges. The second parent value in the commit data stores

gitgitgadget

Hello,

All right.

Jakub Narębski

Yes, we should.

Yes, that's very unfortunate.

Here's a much simpler example:

A commit P has an reasonable commit date (i.e. after release of Git to present) D and has a child commit C with committer date 0. Now, the corrected commiter date of C would D + 1 and the offset would be same too, as the committer date is zero. This overflows as reasonable dates are of the order 2 ^ 34.

To be honest, I would prefer storing corrected committer dates over storing offsets.

While it is 7% of the size of commit-graph file, it is also *only* around ~3.5 MB for a repository of the size of linux kernel (and IIRC correctly, the Windows repo has ~2M commits, it amounts to ~8 MB).

Minimizing space and memory requirements are a top priority, but shouldn't making sure our program is correct and efficient to be a greater priority?

I would love to hear your and Dr. Stolee's opinions on this.

We could modify the graph version in future. Here's how I think it would work:

Graph Version 1, No GDAT -> Topological level
Graph Version 2, GDAT -> Corrected committer dates
Graph Version 3, GDAT -> Generation number v3

and so on.

Of course, we do not have to update generation number definition for each graph version.

However, my statement could still be wrong for things that we do not foresee (similar to how we missed the hard die on different graph version), so I am removing the statement.

Yes, added.

Thanks, fixed!

Thinking about this, I feel creating a new section called "Handling Mixed Generation Number Chains" made more sense:

## Handling Mixed Generation Number Chains

With the introduction of generation number v2 and generation data chunk, the following scenario is possible:

1. "New" Git writes a commit-graph with a GDAT chunk.
2. "Old" Git writes a split commit-graph on top without a GDAT chunk.

The commits in the lower layer will be interpreted as having very large generation values (commit date plus offset) compared to the generation numbers in the top layer (toplogical level). This violates the expectation that the generation of a parent is strictly smaller than the generation of a child. In such cases, we revert to using topological levels for all layers to maintain backwards compatability.

When writing a new layer in split commit-graph, we write a GDAT chunk only if the topmost layer has a GDAT chunk. This guarantees that if a lyer has GDAT chunk, all lower layers must have a GDAT chunk as well.

Rewriting layers follows similar approach: if the topmost layer below set of layers being rewriteen (in the split commit-graph chain) exists, and it does not contain GDAT chunk, then the result of rewrite does not have GDAT chunks either.

Thanks
- Abhishek

Hello,

[...]

No, we need the value of date D that doesn't fit in 2^32 _unsigned_ value, so it needs to be even more in the future than Y2k38 (2038-01-19 03:14:07), which is related to storing date as a _signed_ 32-bit integer

The current-ish Unix epoch time is 1598524281 - let's use it for value of D. Then the offset for commit C would be 1598524282. The current proposal uses 32 bits to store commit date offsets (as unsigned value). The maximum value of offset that we can store is therefore 2^32 - 1, which is 4294967295.

corrected commit date offset(C) = 1,598,524,282
GENERATION_NUMBER_V2_MAX = 4,294,967,295

As you can see there is no overflow in the simplified example.

It is up to 7% of per-commit data, and it doesn't take into account EDGE chunk (for octopus merges), and it doesn't also take into account the size of changed-paths Bloom filters data take in the commit-graph.

On the other hand the case where we would encounter offsets that do not fit in uint32_t is extremply unlikely in sane repositories.

I can think of three solutions:

1. use 64-bit corrected commit dates
- advantages:
* simplest code,
* no need for overflow handling, as we can store all possible values of timestamp_t
- disadvantages:
* commit-graph size increased by up to 7%

2. use 32-bit corrected commit date offsets,
but simply do not store GDAT chunk if there is offset that would not fit in 32-bit wide field
- advantages:
* commit-graph is smaller
* relatively simple overflow handling
- disadvantages:
* performance penalty (generation number v1 vs v2) for abnormal repositories (with overflow not fitting in uint32_t)
* tests would be needed to exercise the overflow code

3. use 32-bit for corrected commit date offset,
with oveflow handling, for example using most significant bit to denote that other bits store position into offset overflow with 64-bits for those offsets that do not fit in 31-bits
- advantages:
* commit-graph is smaller, increasing for abnormal repos
- disadvantages:
* most complex code of all proposed solutions
* smaller overflow limit of 2^31 - 1
* tests would be needed to exercise the overflow code

I think because the situation where we encounter overflow in 32-bit corrected commit date offset is rare, we should go with either 1 or 2 solution.

I have CC-ed Junio C Hamano to ask for his opinion.

So it was about generic mechanism, not something specific to the GDAT chunk.

Good.

[...]

Good idea, and nice writeup.

Best,

Jakub Narębski

I like the idea of this section, and this setup is good.

s/toplogical/topological

But also, we don't want to phrase this as "in this case, we do the wrong thing" but instead

A naive approach of using the newest available generation number from each layer would lead to violated expectations: the lower layer would use corrected commit dates which are much larger than the topological levels of the higher layer. For this reason, Git inspects each layer to see if any layer is missing corrected commit dates. In such a case, Git only uses topological levels.

s/lyer/layer

Perhaps leaving this at a higher level than referencing "GDAT chunk" is advisable. Perhaps use "we write corrected commit dates" or "all lower layers must store corrected commit dates as well", for example.

This could use more positive language to make it clear that sometimes we _do_ want to write corrected commit dates when merging layers:

When merging layers, we do not consider whether the merged layers had corrected commit dates. Instead, the new layer will have corrected commit dates if and only if all existing layers below the new layer have corrected commit dates.

Thanks,
-Stolee

Thanks, that is a great suggestion! Using positive language is more straightforward and easier to understand.

I'm not sure if this level of detail is required in the cover letter for the series, but generation number v2 is corrected commit date; corrected commit date offsets is how we store this value in the commit-graph file.

I would say "committer date heuristics" instead of just "committer date", to be more exact.

Is this data generated using https://github.com/derrickstolee/gen-test
scripts?

It would be nice to have reference email (or other place with details) for "unfortunate problem".

This is a bit of simplification, but good enough for a cover letter.

To be more exact, from various candidates the Corrected Commit Date was chosen. Then it turned out that old Git crashes on changed commit-graph format version value, so if the generation number v2 was to replace v1 it needed to be backward-compatibile: hence the idea of Corrected Commit Date with Monotonically Increasing Offsets. But with GDAT chunk to store generation number v2 (and for the time being leaving generation number v1, i.e. Topological Levels, in CDAT), we are no longer constrained by the requirement of backward-compatibility to make old Git work with commit-graph file created by new Git. So we could go back to Corrected Commit Date, and as you wrote above the backward-compatibile variant performs worse.

Actually it needs to be "corrected commit dates of its parents plus 1" to fulfill the reachability condition for a generation number for a commit:

A can reach B => gen(A) < gen(B)

Of course it can be computed in simpler way, because

max_P (gen(P) + 1) == max_P (gen(P)) + 1

All right.

All right.

However I think the cover letter should also describe what should happen in a mixed version environment (for example new Git on command line, copy of old Git used by GUI client), and in particular what should happen in a mixed-chain case - both for reading and for writing the commit-graph file.

For *writing*: because old Git would create commit-graph layers without the GDAT chunk, to simplify the behavior and make easy to reason about commit-graph data (the situation should be not that common, and transient -- it should get more rare as the time goes), we want the following behavior from new Git:

- If top layer contains the GDAT chunk, or we are rewriting commit-graph file (--split=replace), or we are merging layers and there are no layers without GDAT chunk below set of layers that are merged, then

write commit-graph file or commit-graph layer with GDAT chunk,

otherwise

write commit-graph layer without GDAT chunk.

This means that there are commit-graph layers without GDAT chunk if and only if the top layer is also without GDAT chunk.

For *reading* we want to use generation number v2 (corrected commit date) if possible, and fall back to generation number v1 (topological levels).

- If the top layer contains the GDAT chunk (or maybe even if the topmost layer that involves all commits in question, not necessarily the top layer in the full commit-graph chain), then use generation number v2

- commit_graph_data->generation stores corrected commit date, computed as sum of committer date (from CDAT) and offset (from GDAT)

- A can reach B => gen(A) < gen(B)

- there is no need for committer date heuristics, and no need for limiting use of generation number to where there is a cutoff (to not hamper performance).

- If there are layers without GDAT chunks, which thanks to the write behavior means simply top layer without GDAT chunk, we need to turn off use of generation numbers or fall back to using topological levels

- commit_graph_data->generation stores topological levels, taken from CDAT chunk (30-bits)

- A can reach B => gen(A) < gen(B)

- we probably want to keep tie-breaking of sorting by generation number via committer date, and limit use of generation number as opposed to using committer date heuristics (with slop) to not make performance worse.

If I remember it correctly this was done to always store in GDAT chunk corrected commit date offsets, isn't it?

All right.

I think it might be good idea to split off the change to tar file tests (as a preparatory patch), to make reviews and bisecting easier.

Do we also test for proper merging of split commit-graph layers, not only adding a new layer and a full rewrite (--split=replace)?

That is good for performance.

Good.

Good, that is needed for testing mixed-version behavior.

All right, but see the caveat.

Always a good thing.

Where by "version" you mean generation number version - the commit-graph version number unfortunately needs to stay the same...

                                ^^^^^^

Something missing in this point, the sentence ends abruptly.

Thanks.

It is usually better to keep the commits small. Good.

Good work!

[...]

Best,
--
Jakub Narębski

This seems very sane to me, and I'd be glad to see it spelled out in more specific detail. I was wondering this myself, and had to double check with Stolee off-list that my interpretation of Abhishek's code was correct.

But yes, only writing GDAT chunks when all layers in the chain have GDAT chunks makes sense, since we can't interoperate between corrected dates and topological levels. Since we can't fill in the GDAT data of layers generated in pre-GDAT versions of Git without invalidating the GDAT layers on-disk, there's no point to speculatively computing both chunks.

Merging rules are obviously correct, which is good. For what it's worth, the '--split=replace' case is what we'll really care about at GitHub, since it's unlikely we'd drop all existing commit-graph chains and rebuild them from scratch. More likely is that we'll let the new GDAT chunks trickle in over time when we run 'git commit-graph write' with '--split=replace', which happens "every so often".

I don't follow this. If we have a multi-layer chain, either all or none of the layers have a GDAT chunk. So, "if the top layer contains the GDAT chunk" makes sense, since it implies that all layers have the GDAT chunk. I don't see how "even if the topmost layer that involves all commits in question" would be possible, since (if I'm understanding your description correctly), we can't have *some* of the layers having a GDAT chunk with others only having a CDAT chunk.

I'm a little confused here.

Good, I'm glad that this can be a quick check (that we can cache for future reads, but I'm not even sure the caching would be necessary without measuring).

All makes very good sense, except for the one point I raised above.

Thanks, Abhishek for your great work on this. I was feeling bad that I wasn't more involved in the early discussions about the transition plan, but what you, Stolee, and Jakub came up with all seems like what I would have suggested, anyway ;-).

Thanks,
Taylor

To be more detailed, without '--split=replace' we would want the following layer merging behavior:

[layer with GDAT][with GDAT][without GDAT][without GDAT][without GDAT]

In the split commit-graph chain above, merging two topmost layers should create a layer without GDAT; merging three topmost layers (and any other layers, e.g. two middle ones) should create a layer
with GDAT.

This is only speculative, and most probably totally unnecessary complication (either that, or something that we would get for free). Assume that the command in question operates only on historical data; for example git log --topo-order HEAD~1000. If all commits (or, what's equivalent, most recent commits i.e. HEAD~1000) have their data in split commit-graph layers with GDAT, we can theoretically use generation number v2, even if there are some newer commits that have their data in layers without GDAT (and some even newer ones outside commit-graph files).

I hope that this explains my (possibly harebrained) idea.

There is a question where to store the information that we cannot use generation number v2 (that 'generation' contains topological levels and not corrected commit date):
- create new global variable
- store it in struct split_commit_graph_opts
- set chunk_generation_data to NULL for all graphs
in chain (it is in struct commit_graph)?

Thank you for your work on improving this feature.

Best,

Jakub Narebski

Yes, it is.

Will add.

Yes, definitely. Will add

The current implementation checks the entire chain for GDAT, rather than just the topmost layer as we cannot assert that g would be the topmost layer of the chain.

See the discussion here: https://lore.kernel.org/git/20200814045957.GA1380@Abhishek-Arch/

It's one of drawbacks of having a single member 64-bit generation instead of two 32-bit members level and odate.

Yes.

We do not, will add a test at end. Thanks for pointing this out.

Yes, clarified.

I didn't finish the sentence. Meant to say:

- Improve commit messages for "commit-graph: fix regression when computing bloom filter", "commit-graph: consolidate fill_commit_graph_info",

Hello,

Here is a summary of my comments and thoughts after carefully reviewing all patches in the series.

[...]

I see that it is defined correctly in the documentation, which is more important than cover letter (which would not be stored in the repository for memory, even in the commit message for the merge).

[...]

Actually we can simplify handling of merging layers, while still retaining the property that in mixed-version chain all GDAT-full layers are before / below GDAT-less layers.

Namely, if merging layers, and at least one layer being merged doesn't have GDAT chunk, then the result of merge wouldn't have either.

We can always switch to slightly more complicated behavior proposed above in quoted part later, perhaps as a followup commit.

This might be not necessary if Git would always check the whole chain of split commit-graph layers for presence of GDAT-less layers.

But I still think it is a good idea to avoid having GDAT-less "holes".

Or stored directly in GDAT, at the cost of increasing the file size by at most 7% (if I have done my math correctly).

See also the issue with clamping offsets (GENERATION_NUMBER_V2_OFFSET_MAX).

And this is being done in this patch series. Good!

The thing I was worrying about turned out to be non-issue, as the comparison function in question is used only when writing, and in this case we have corrected commit date computer - though perhaps not being written (as far as I understand it, but I might be mistaken).

[...]

No problems, maybe just expanding a commit message and/or adding a comment.

Looks good to me.

I think this commit could be split into three:
- fix to the 'generate tar with future mtime' test
as it is a hidden bug (when using commit-graph)
- simplify implementation of fill_commit_in_graph() by using fill_commit_graph_info()
- move loading date into fill_commit_graph_info() that uncovers the issue with 'generate tar with future mtime'

On the other hand because they are inter-related, those changes might be kept in a single commit.

In commit message greater care needs to be taken with fill_commit_graph_info() and fill_commit_in_graph(), when to use one and when to use the other. For example it is fill_commit_graph_info() that changes its behavior, and it is fill_commit_in_graph() that is getting simplified.

Looks good to me, though it might be good idea to add comments about the sorting order (inside comment) to appropriate header files.

This conversion misses one place, though it would be changed to use topological levels slab in next patch.

This patch also unnecessary introduces GENERATION_NUMBER_V1_INFINITY. There is no need for it: generation field can always simply use GENERATION_NUMBER_INFINITY for commits not in commit-graph.

This is the patch that needs GENERATION_NUMBER_V1_INFINITY (or TOPOLOGICAL_LEVEL_INFINITY), not the previous patch.

Detailed analysis uncovered hidden bug in the code of compute_generation_numbers() that works only because of historical reasons (that topological levels in Git start from 1, not from 0). The problem is that the 'level' / 'generation' variable for commits not in graph, and therefore ones that needs to have its generation number computed, is 0 (default value on commit slab) and not GENERATION_NUMBER*_INFINITY as it should.

This issue is present since moving commit graph info data to commit-slab. We can simply document it and ignore (it works, if by accident), or try to fix it.

We need to handle GENERATION_NUMBER*_MAX clamping carefully in the future patches.

I think also that this patch needs a bit more detailed commit message.

Looks good, though verify_commit_graph() now verifies *a* generation number used, be it v1 (topological level) or v2 (corrected commit date), so the variable rename is unnecessary. We verify that they fulfill the reachability condition promise, that is gen(parent) <= gen(commit), (the '=' is to include GENERATION_NUMBER*_MAX case), as it is what is used to speed up graph traversal.

We probably want to verify both topological level values in CDAT, and if they exist also corrected commit date values in GDAT. But that might be left for the future commit.

To save up to 6-7% on commit-graph file size we store 32-bits corrected commit date offsets, instead of storing 64-bits corrected commit date.

However, as far as I understand it, using non-monotonic values for on-disk storage with limited field size, like 32-bits corrected commit date offset, leads to problems with GENERATION_NUMBER*_MAX. Namely, as I have written in detail in my reply to patch 11/11 in this series, there is no way to fulfill the reachability condition promise if we have to store offset which true value do not fit in 32-bits reserved for it.

This is extremly unlikely to happen in practice, but we need to be able to handle it somehow. We can store 64-bit corrected commit date, which has graph-monotonic values, and the problem goes away in theory and in practice (we would never have values that do not fit). We can keep storing 32-bit offsets, and simply do not use GDAT chunk if there is offset value that do not fit.

All this of course, provided that I am not wrong about this issue...

The commit message do not say anything about the *writing* side.

However, if we want to keep the requirement that GDAT-less layers in the split commit-graph chain must all be above any GDAT-containing layers, we need to consider how we want layer merging to behave. We could either opt for using GDAT whenever possible, or similify code and skip using GDAT if we are unsure.

The first approach would mean that if the topmost layer below set of layers being rewritten (in the split commit-graph chain) exists, and it does not contain GDAT chunk, then and only then the result of rewrite should not have GDAT chunk either.

The second approach is, I think, simpler: if any of layers that is being rewritten is GDAT-less (we need to check only the top layer, though), and we are not running full rewrite ('--split=replace'), then the result of rewrite should not have GDAT chunk either. We can switch to the first algorithm in later commit.

Whether we choose one or the other, we need test that doing layer merging do not break GDAT-inness requirement stated above.

Also, we can probably test that we are not using v1 and v2 at the same time with tests involving --is-ancestor, or --contains / --merged.

I think this commit could be split into two:
- disable commit graph for entire t6024-recursive-merge test
- use corrected commit dates in paint_down_to_common()

On the other hand because they are inter-related, those changes might be better kept in a single commit.

It would be nice to have some benchmark data, or at least stating that performance does not change (within the error bounds), using for example 'git merge-base v4.8 v4.9' in Linux kernel repository.

Looks good, there are a few places where 'generation number' (referring to the v1 version) should have been replaced with 'topological level'.

I am also unsure how the GDAT chunk can be "later modified to store future generation number related data.". I'd like to have an example, or for this statement to be removed (if it turns out to not be true, not without introducing yet another chunk type).

Thanks for all your work.

Best regards,
--
Jakub Narębski

Hello,

Thanks for the detailed review. It must have taken you a lot of time and focus to go through the patches, so I have really appreciate the effort.

I have been going over the comments and they are reasonable and very much needed. I will respond to the mails in the specific threads (to keep the discussion locally scoped and thus manageable), with doubts and comments that I have as I try to follow through the suggestions.

Thanks
- Abhishek

This patch series implements the corrected commit date offsets as generation number v2, along with other pre-requisites.

Git uses topological levels in the commit-graph file for commit-graph traversal operations like git log --graph. Unfortunately, using topological levels can result in a worse performance than without them when compared with committer date as a heuristics. For example, git merge-base v4.8 v4.9 on the Linux repository walks 635,579 commits using topological levels and walks 167,468 using committer date.

Thus, the need for generation number v2 was born. New generation number needed to provide good performance, increment updates, and backward compatibility. Due to an unfortunate problem 1
[https://public-inbox.org/git/[email protected]/], we also needed a way to distinguish between the old and new generation number without incrementing graph version.

Various candidates were examined (https://github.com/derrickstolee/gen-test,
https://github.com/abhishekkumar2718/git/pull/1). The proposed generation number v2, Corrected Commit Date with Mononotically Increasing Offsets performed much worse than committer date (506,577 vs. 167,468 commits walked for git merge-base v4.8 v4.9) and was dropped.

Using Generation Data chunk (GDAT) relieves the requirement of backward compatibility as we would continue to store topological levels in Commit Data (CDAT) chunk. Thus, Corrected Commit Date was chosen as generation number v2. The Corrected Commit Date is defined as:

For a commit C, let its corrected commit date be the maximum of the commit date of C and the corrected commit dates of its parents plus 1. Then corrected commit date offset is the difference between corrected commit date of C and commit date of C. As a special case, a root commit with timestamp zero has corrected commit date of 1 to be able distinguish it from GENERATION_NUMBER_ZERO (that is, an uncomputed corrected commit date).

We will introduce an additional commit-graph chunk, Generation Data chunk, and store corrected commit date offsets in GDAT chunk while storing topological levels in CDAT chunk. The old versions of Git would ignore GDAT chunk, using topological levels from CDAT chunk. In contrast, new versions of Git would use corrected commit dates, falling back to topological level if the generation data chunk is absent in the commit-graph file.

While storing corrected commit date offsets saves us 4 bytes per commit (as compared with storing corrected commit dates directly), it's possible for the offset to overflow the space allocated. To handle such cases, we introduce a new chunk, Generation Data Overflow (GDOV) that stores the corrected commit date. For overflowing offsets, we set MSB and store the position into the GDOV chunk, in a mechanism similar to the Extra Edges list chunk.

For mixed generation number environment (for example new Git on the command line, old Git used by GUI client), we can encounter a mixed-chain commit-graph (a commit-graph chain where some of split commit-graph files have GDAT chunk and others do not). As backward compatibility is one of the goals, we can define the following behavior:

While reading a mixed-chain commit-graph version, we fall back on topological levels as corrected commit dates and topological levels cannot be compared directly.

While writing on top of a split commit-graph, we check if the tip of the chain has a GDAT chunk. If it does, we append to the chain, writing GDAT chunk. Thus, we guarantee if the topmost split commit-graph file has a GDAT chunk, rest of the chain does too.

If the topmost split commit-graph file does not have a GDAT chunk (meaning it has been appended by the old Git), we write without GDAT chunk. We do write a GDAT chunk when the existing chain does not have GDAT chunk - when we are writing to the commit-graph chain with the 'replace' strategy.

Thanks to Dr. Stolee, Dr. Narębski, and Taylor for their reviews.

I look forward to everyone's reviews!

Thanks

* Abhishek

----------------------------------------------------------------------------

Changes in version 4:

* Added GDOV to handle overflows in generation data.
* Added a test for writing tip graph for a generation number v2 graph chain in t5324-split-commit-graph.sh
* Added a section on how mixed generation number chains are handled in Documentation/technical/commit-graph-format.txt
* Reverted unimportant whitespace, style changes in commit-graph.c
* Added header comments about the order of comparision for compare_commits_by_gen_then_commit_date in commit.h, compare_commits_by_gen in commit-graph.h
* Elaborated on why t6404 fails with corrected commit date and must be run with GIT_TEST_COMMIT_GRAPH=1in the commit "commit-reach: use corrected commit dates in paint_down_to_common()"
* Elaborated on write behavior for mixed generation number chains in the commit "commit-graph: use generation v2 only if entire chain does"
* Added notes about adding the topo_level slab to struct write_commit_graph_context as well as struct commit_graph.
* Clarified commit message for "commit-graph: consolidate fill_commit_graph_info"
* Removed the claim "GDAT can store future generation numbers" because it hasn't been tested yet.

Changes in version 3:

* Reordered patches as discussed in 2
[https://lore.kernel.org/git/[email protected]/]
.
* Split "implement corrected commit date" into two patches - one introducing the topo level slab and other implementing corrected commit dates.
* Extended split-commit-graph tests to verify at the end of test.
* Use topological levels as generation number if any of split commit-graph files do not have generation data chunk.

Changes in version 2:

* Add tests for generation data chunk.
* Add an option GIT_TEST_COMMIT_GRAPH_NO_GDAT to control whether to write generation data chunk.
* Compare commits with corrected commit dates if present in paint_down_to_common().
* Update technical documentation.
* Handle mixed generation commit chains.
* Improve commit messages for "commit-graph: fix regression when computing bloom filter", "commit-graph: consolidate fill_commit_graph_info",
* Revert unnecessary whitespace changes.
* Split uint_32 -> timestamp_t change into a new commit.

Abhishek Kumar (10):
commit-graph: fix regression when computing Bloom filters
revision: parse parent in indegree_walk_step()
commit-graph: consolidate fill_commit_graph_info
commit-graph: return 64-bit generation number
commit-graph: add a slab to store topological levels
commit-graph: implement corrected commit date
commit-graph: implement generation data chunk
commit-graph: use generation v2 only if entire chain does
commit-reach: use corrected commit dates in paint_down_to_common()
doc: add corrected commit date info

 .../technical/commit-graph-format.txt         |  21 +-
 Documentation/technical/commit-graph.txt      |  62 ++++-
 commit-graph.c                                | 256 ++++++++++++++----
 commit-graph.h                                |  17 +-
 commit-reach.c                                |  38 +--
 commit-reach.h                                |   2 +-
 commit.c                                      |   4 +-
 commit.h                                      |   5 +-
 revision.c                                    |  13 +-
 t/README                                      |   3 +
 t/helper/test-read-graph.c                    |   4 +
 t/t4216-log-bloom.sh                          |   4 +-
 t/t5000-tar-tree.sh                           |  20 +-
 t/t5318-commit-graph.sh                       |  70 ++++-
 t/t5324-split-commit-graph.sh                 |  98 ++++++-
 t/t6404-recursive-merge.sh                    |   5 +-
 t/t6600-test-reach.sh                         |  68 ++---
 upload-pack.c                                 |   2 +-
 18 files changed, 534 insertions(+), 158 deletions(-)

base-commit: d98273ba77e1ab9ec755576bc86c716a97bf59d7
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-676%2Fabhishekkumar2718%2Fcorrected_commit_date-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-676/abhishekkumar2718/corrected_commit_date-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/676

Range-diff vs v3:

1: c6b7ade7af ! 1: fae81b534b commit-graph: fix regression when computing bloom filter
@@ Metadata
Author: Abhishek Kumar <[email protected]>

## Commit message ##
- commit-graph: fix regression when computing bloom filter
+ commit-graph: fix regression when computing Bloom filters

commit_gen_cmp is used when writing a commit-graph to sort commits in generation order before computing Bloom filters. Since c49c82aa (commit:
@@ Commit message
'commit_graph_data_at(c)->generation') in order to access it while writing.

+ While measuring performance with `git commit-graph write --reachable
+ --changed-paths` on the linux repository led to around 1m40s for both
+ HEAD and master (and could be due to fault in my measurements), it is
+ still the "right" thing to do.
+

## commit-graph.c ##
2: e673867234 ! 2: 4470d91642 revision: parse parent in indegree_walk_step()

     @@ revision.c: static void indegree_walk_step(struct rev_info *revs)
       		struct commit *parent = p->item;
       		int *pi = indegree_slab_at(&info->indegree, parent);
       
     -+		if (parse_commit_gently(parent, 1) < 0)
     ++		if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
      +			return;
      +
       		if (*pi)

3: 18d5864f81 ! 3: 18bb3318a1 commit-graph: consolidate fill_commit_graph_info
@@ Commit message
implementation by calling fill_commit_graph_info() within fill_commit_in_graph().

- The test 'generate tar with future mtime' creates a commit with commit
- time of (2 ^ 36 + 1) seconds since EPOCH. The commit time overflows into
- generation number (within CDAT chunk) and has undefined behavior.
+ fill_commit_graph_info() used to not load committer data from commit data
+ chunk. However, with the corrected committer date, we have to load
+ committer date to calculate generation number value.

- The test used to pass as fill_commit_in_graph() guarantees the values of
- graph position and generation number, and did not load timestamp.
- However, with corrected commit date we will need load the timestamp as
- well to populate the generation number.
+ e51217e15 (t5000: test tar files that overflow ustar headers,
+ 30-06-2016) introduced a test 'generate tar with future mtime' that
+ creates a commit with committer date of (2 ^ 36 + 1) seconds since
+ EPOCH. The CDAT chunk provides 34-bits for storing committer date, thus
+ committer time overflows into generation number (within CDAT chunk) and
+ has undefined behavior.

- Let's fix the test by setting a timestamp of (2 ^ 34 - 1) seconds.
+ The test used to pass as fill_commit_graph_info() would not set struct
+ member date of struct commit and loads committer date from the object
+ database, generating a tar file with the expected mtime.
+
+ However, with corrected commit date, we will load the committer date
+ from CDAT chunk (truncated to lower 34-bits to populate the generation
+ number. Thus, Git sets date and generates tar file with the truncated
+ mtime.
+
+ The ustar format (the header format used by most modern tar programs)
+ only has room for 11 (or 12, depending om some implementations) octal
+ digits for the size and mtime of each files.
+
+ Thus, setting a timestamp of 2 ^ 33 + 1 would overflow the 11-octal
+ digit implementations while still fitting into commit data chunk.
+
+ Since we want to test 12-octal digit implementations of ustar as well,
+ let's modify the existing test to no longer use commit-graph file.

@@ commit-graph.c: static int fill_commit_in_graph(struct repository *r,
- graph_data->graph_pos = pos;
lex_index = pos - g->num_commits_in_base;
-
-- commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
-+ commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
+ commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;

item->object.parsed = 1;

@@ commit-graph.c: static int fill_commit_in_graph(struct repository *r,
edge_value = get_be32(commit_data + g->hash_len);

## t/t5000-tar-tree.sh ##
-@@ t/t5000-tar-tree.sh: test_expect_success TIME_IS_64BIT 'set up repository with far-future commit' ' +@@ t/t5000-tar-tree.sh: test_expect_success TAR_HUGE,LONG_IS_64BIT 'system tar can read our huge size' '
+ test_cmp expect actual
+ '
+
++test_expect_success TIME_IS_64BIT 'set up repository with far-future commit' '
++ rm -f .git/index &&
++ echo foo >file &&
++ git add file &&
++ GIT_COMMITTER_DATE="@17179869183 +0000" \
++ git commit -m "tempori parendum"
++'
++
++test_expect_success TIME_IS_64BIT 'generate tar with future mtime' '
++ git archive HEAD >future.tar
++'
++
++test_expect_success TAR_HUGE,TIME_IS_64BIT,TIME_T_IS_64BIT 'system tar can read our future mtime' '
++ echo 2514 >expect &&
++ tar_info future.tar | cut -d" " -f2 >actual &&
++ test_cmp expect actual
++'
++
+ test_expect_success TIME_IS_64BIT 'set up repository with far-future commit' '
rm -f .git/index &&
echo content >file &&
git add file &&
- GIT_COMMITTER_DATE="@68719476737 +0000" \
-+ GIT_COMMITTER_DATE="@17179869183 +0000" \
++ GIT_TEST_COMMIT_GRAPH=0 GIT_COMMITTER_DATE="@68719476737 +0000" \
git commit -m "tempori parendum"
'

-@@ t/t5000-tar-tree.sh: test_expect_success TIME_IS_64BIT 'generate tar with future mtime' '
- '
-
- test_expect_success TAR_HUGE,TIME_IS_64BIT,TIME_T_IS_64BIT 'system tar can read our future mtime' '
-- echo 4147 >expect &&
-+ echo 2514 >expect &&
- tar_info future.tar | cut -d" " -f2 >actual &&
- test_cmp expect actual
- '

  4:  6a0cde983d <  -:  ---------- commit-graph: consolidate compare_commits_by_gen
  5:  6be759a954 !  4:  011b0aa497 commit-graph: return 64-bit generation number

@@ Commit message
commit_graph_generation(), use timestamp_t for local variables and define GENERATION_NUMBER_INFINITY as (2 ^ 63 - 1) instead.

+ We rename GENERATION_NUMBER_MAX to GENERATION_NUMBER_V1_MAX to
+ represent the largest topological level we can store in the commit data
+ chunk.
+
+ With corrected commit dates implemented, we will have two such *_MAX
+ variables to denote the largest offset and largest topological level
+ that can be stored.
+

## commit-graph.c ##
@@ commit-graph.c: uint32_t commit_graph_position(const struct commit *c)
{
struct commit_graph_data *data =
commit_graph_data_slab_peek(&commit_graph_data_slab, c);
-@@ commit-graph.c: uint32_t commit_graph_generation(const struct commit *c)
- int compare_commits_by_gen(const void *_a, const void *_b)
- {
- const struct commit *a = _a, *b = _b;
-- const uint32_t generation_a = commit_graph_generation(a);
-- const uint32_t generation_b = commit_graph_generation(b);
-+ const timestamp_t generation_a = commit_graph_generation(a);
-+ const timestamp_t generation_b = commit_graph_generation(b);
-
- /* older commits first */
- if (generation_a < generation_b)
@@ commit-graph.c: static int commit_gen_cmp(const void *va, const void *vb)
const struct commit *a = *(const struct commit **)va;
const struct commit *b = *(const struct commit **)vb;
@@ commit-graph.c: static int commit_gen_cmp(const void *va, const void *vb)
if (generation_a < generation_b)
return -1;
@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
- uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
+ _("Computing commit graph generation numbers"),
+ ctx->commits.nr);
+ for (i = 0; i < ctx->commits.nr; i++) {
+- uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
++ timestamp_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;

display_progress(ctx->progress, i + 1);
-- if (generation != GENERATION_NUMBER_INFINITY &&
-+ if (generation != GENERATION_NUMBER_V1_INFINITY &&
- generation != GENERATION_NUMBER_ZERO)
- continue;
-
+ if (generation != GENERATION_NUMBER_INFINITY &&
@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
- for (parent = current->parents; parent; parent = parent->next) {
- generation = commit_graph_data_at(parent->item)->generation;
-
-- if (generation == GENERATION_NUMBER_INFINITY ||
-+ if (generation == GENERATION_NUMBER_V1_INFINITY ||
- generation == GENERATION_NUMBER_ZERO) {
- all_parents_computed = 0;
- commit_list_insert(parent->item, &list);
+ data->generation = max_generation + 1;
+ pop_commit(&list);
+
+- if (data->generation > GENERATION_NUMBER_MAX)
+- data->generation = GENERATION_NUMBER_MAX;
++ if (data->generation > GENERATION_NUMBER_V1_MAX)
++ data->generation = GENERATION_NUMBER_V1_MAX;
+ }
+ }
+ }
@@ commit-graph.c: int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
for (i = 0; i < g->num_commits; i++) {
struct commit *graph_commit, *odb_commit;
@@ commit-graph.c: int verify_commit_graph(struct repository *r, struct commit_grap

display_progress(progress, i + 1);
hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
+@@ commit-graph.c: int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
+ continue;
+
+ /*
+- * If one of our parents has generation GENERATION_NUMBER_MAX, then
+- * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
++ * If one of our parents has generation GENERATION_NUMBER_V1_MAX, then
++ * our generation is also GENERATION_NUMBER_V1_MAX. Decrement to avoid
+ * extra logic in the following condition.
+ */
+- if (max_generation == GENERATION_NUMBER_MAX)
++ if (max_generation == GENERATION_NUMBER_V1_MAX)
+ max_generation--;
+
+ generation = commit_graph_generation(graph_commit);

## commit-graph.h ##
@@ commit-graph.h: void disable_commit_graph(struct repository *r);
@@ commit-graph.h: void disable_commit_graph(struct repository *r);
-uint32_t commit_graph_generation(const struct commit *); +timestamp_t commit_graph_generation(const struct commit *);
uint32_t commit_graph_position(const struct commit *);
-
- int compare_commits_by_gen(const void *_a, const void *_b);
+ #endif

## commit-reach.c ##
@@ commit-reach.c: static int queue_has_nonstale(struct prio_queue *queue)
@@ commit-reach.c: int repo_in_merge_bases_many(struct repository *r, struct commit
{
struct commit_list *bases;
int ret = 0, i;
-- uint32_t generation, min_generation = GENERATION_NUMBER_INFINITY;
-+ timestamp_t generation, min_generation = GENERATION_NUMBER_INFINITY;
+- uint32_t generation, max_generation = GENERATION_NUMBER_ZERO;
++ timestamp_t generation, max_generation = GENERATION_NUMBER_INFINITY;

if (repo_parse_commit(r, commit))
return ret;
@@ commit-reach.c: static enum contains_result contains_tag_algo(struct commit *can
struct commit *c = p->item; load_commit_graph_info(the_repository, c);
generation = commit_graph_generation(c);
+@@ commit-reach.c: static int compare_commits_by_gen(const void *_a, const void *_b)
+ const struct commit *a = *(const struct commit * const *)_a;
+ const struct commit *b = *(const struct commit * const *)_b;
+
+- uint32_t generation_a = commit_graph_generation(a);
+- uint32_t generation_b = commit_graph_generation(b);
++ timestamp_t generation_a = commit_graph_generation(a);
++ timestamp_t generation_b = commit_graph_generation(b);
+
+ if (generation_a < generation_b)
+ return -1;
@@ commit-reach.c: int can_all_from_reach_with_flag(struct object_array *from,
unsigned int with_flag,
unsigned int assign_flag,
@@ commit-reach.h: int can_all_from_reach_with_flag(struct object_array *from,
int commit_date_cutoff);

+ ## commit.c ##
+@@ commit.c: int compare_commits_by_author_date(const void *a_, const void *b_,
+ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
+ {
+ const struct commit *a = a_, *b = b_;
+- const uint32_t generation_a = commit_graph_generation(a),
+- generation_b = commit_graph_generation(b);
++ const timestamp_t generation_a = commit_graph_generation(a),
++ generation_b = commit_graph_generation(b);
+
+ /* newer commits first */
+ if (generation_a < generation_b)
+
## commit.h ##
@@
#include "commit-slab.h"

#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
-#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF
+-#define GENERATION_NUMBER_MAX 0x3FFFFFFF
+#define GENERATION_NUMBER_INFINITY ((1ULL << 63) - 1)
-+#define GENERATION_NUMBER_V1_INFINITY 0xFFFFFFFF
- #define GENERATION_NUMBER_MAX 0x3FFFFFFF ++#define GENERATION_NUMBER_V1_MAX 0x3FFFFFFF #define GENERATION_NUMBER_ZERO 0

+ struct commit_list {

## revision.c ##
@@ revision.c: define_commit_slab(indegree_slab, int);
@@ revision.c: static void init_topo_walk(struct rev_info *revs)
- uint32_t generation;
+ timestamp_t generation;

- if (parse_commit_gently(c, 1))
+ if (repo_parse_commit_gently(revs->repo, c, 1))
continue;
@@ revision.c: static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
for (p = commit->parents; p; p = p->next) {
6: b347dbb01b ! 5: e067f653ad commit-graph: add a slab to store topological levels

     @@ Metadata
       ## Commit message ##
          commit-graph: add a slab to store topological levels
      
     -    As we are writing topological levels to commit data chunk to ensure
     -    backwards compatibility with "Old" Git and the member `generation` of
     -    struct commit_graph_data will store corrected commit date in a later
     -    commit, let's introduce a commit-slab to store topological levels while
     -    writing commit-graph.
     +    In a later commit we will introduce corrected commit date as the
     +    generation number v2. This value will be stored in the new seperate
     +    Generation Data chunk. However, to ensure backwards compatibility with
     +    "Old" Git we need to continue to write generation number v1, which is
     +    topological level, to the commit data chunk. This means that we need to
     +    compute both versions of generation numbers when writing the
     +    commit-graph file. Therefore, let's introduce a commit-slab to store
     +    topological levels; corrected commit date will be stored in the member
     +    `generation` of struct commit_graph_data.
      
          When Git creates a split commit-graph, it takes advantage of the
          generation values that have been computed already and present in
          existing commit-graph files.
      
     -    So, let's add a pointer to struct commit_graph to the topological level
     -    commit-slab and populate it with topological levels while writing a
     -    split commit-graph.
     +    So, let's add a pointer to struct commit_graph as well as struct
     +    write_commit_graph_context to the topological level commit-slab
     +    and populate it with topological levels while writing a commit-graph
     +    file.
      
          Signed-off-by: Abhishek Kumar <[email protected]>
      
     @@ commit-graph.c: struct write_commit_graph_context {
       		 order_by_pack:1;
       
      +	struct topo_level_slab *topo_levels;
     - 	const struct split_commit_graph_opts *split_opts;
     + 	const struct commit_graph_opts *opts;
       	size_t total_bloom_filter_data_size;
       	const struct bloom_filter_settings *bloom_settings;
      @@ commit-graph.c: static int write_graph_chunk_data(struct hashfile *f,
     @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
       					_("Computing commit graph generation numbers"),
       					ctx->commits.nr);
       	for (i = 0; i < ctx->commits.nr; i++) {
     --		uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
     -+		uint32_t level = *topo_level_slab_at(ctx->topo_levels, ctx->commits.list[i]);
     +-		timestamp_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
     ++		timestamp_t level = *topo_level_slab_at(ctx->topo_levels, ctx->commits.list[i]);
       
       		display_progress(ctx->progress, i + 1);
     --		if (generation != GENERATION_NUMBER_V1_INFINITY &&
     +-		if (generation != GENERATION_NUMBER_INFINITY &&
      -		    generation != GENERATION_NUMBER_ZERO)
     -+		if (level != GENERATION_NUMBER_V1_INFINITY &&
     ++		if (level != GENERATION_NUMBER_INFINITY &&
      +		    level != GENERATION_NUMBER_ZERO)
       			continue;
       
     @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
      -				generation = commit_graph_data_at(parent->item)->generation;
      +				level = *topo_level_slab_at(ctx->topo_levels, parent->item);
       
     --				if (generation == GENERATION_NUMBER_V1_INFINITY ||
     +-				if (generation == GENERATION_NUMBER_INFINITY ||
      -				    generation == GENERATION_NUMBER_ZERO) {
     -+				if (level == GENERATION_NUMBER_V1_INFINITY ||
     ++				if (level == GENERATION_NUMBER_INFINITY ||
      +				    level == GENERATION_NUMBER_ZERO) {
       					all_parents_computed = 0;
       					commit_list_insert(parent->item, &list);
     @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
      -				data->generation = max_generation + 1;
       				pop_commit(&list);
       
     --				if (data->generation > GENERATION_NUMBER_MAX)
     --					data->generation = GENERATION_NUMBER_MAX;
     -+				if (max_level > GENERATION_NUMBER_MAX - 1)
     -+					max_level = GENERATION_NUMBER_MAX - 1;
     +-				if (data->generation > GENERATION_NUMBER_V1_MAX)
     +-					data->generation = GENERATION_NUMBER_V1_MAX;
     ++				if (max_level > GENERATION_NUMBER_V1_MAX - 1)
     ++					max_level = GENERATION_NUMBER_V1_MAX - 1;
      +				*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
       			}
       		}
       	}
      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
     - 	uint32_t i, count_distinct = 0;
       	int res = 0;
       	int replace = 0;
     + 	struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
      +	struct topo_level_slab topo_levels;
       
       	if (!commit_graph_compatible(the_repository))
       		return 0;
      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
     - 		}
     - 	}
     + 							 bloom_settings.max_changed_paths);
     + 	ctx->bloom_settings = &bloom_settings;
       
      +	init_topo_level_slab(&topo_levels);
      +	ctx->topo_levels = &topo_levels;
     @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
      +		}
      +	}
      +
     - 	if (pack_indexes) {
     - 		ctx->order_by_pack = 1;
     - 		if ((res = fill_oids_from_packs(ctx, pack_indexes)))
     + 	if (flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS)
     + 		ctx->changed_paths = 1;
     + 	if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
      
       ## commit-graph.h ##
      @@ commit-graph.h: struct commit_graph {
     @@ commit-graph.h: struct commit_graph {
       	struct bloom_filter_settings *bloom_filter_settings;
       };
       
     -
     - ## commit.h ##
     -@@
     - #define GENERATION_NUMBER_V1_INFINITY 0xFFFFFFFF
     - #define GENERATION_NUMBER_MAX 0x3FFFFFFF
     - #define GENERATION_NUMBER_ZERO 0
     -+#define GENERATION_NUMBER_V2_OFFSET_MAX 0xFFFFFFFF
     - 
     - struct commit_list {
     - 	struct commit *item;

7: 4074ace65b ! 6: 694ef1ec08 commit-graph: implement corrected commit date
@@ Commit message
the maximum of its commit date and one more than the largest corrected commit date among its parents.

+ As a special case, a root commit with timestamp of zero (01.01.1970
+ 00:00:00Z) has corrected commit date of one, to be able to distinguish
+ from GENERATION_NUMBER_ZERO (that is, an uncomputed corrected commit
+ date).
+
To minimize the space required to store corrected commit date, Git stores corrected commit date offsets into the commit-graph file. The corrected commit date offset for a commit is defined as the difference between its corrected commit date and actual commit date.

+ Storing corrected commit date requires sizeof(timestamp_t) bytes, which
+ in most cases is 64 bits (uintmax_t). However, corrected commit date
+ offsets can be safely stored using only 32-bits. This halves the size
+ of GDAT chunk, which is a reduction of around 6% in the size of
+ commit-graph file.
+
+ However, using offsets be problematic if one of commits is malformed but
+ valid and has committerdate of 0 Unix time, as the offset would be the
+ same as corrected commit date and thus require 64-bits to be stored
+ properly.
+
While Git does not write out offsets at this stage, Git stores the
corrected commit dates in member generation of struct commit_graph_data.
It will begin writing commit date offsets with the introduction of
@@ commit-graph.c: static int commit_gen_cmp(const void *va, const void *vb)
@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
ctx->commits.nr);
for (i = 0; i < ctx->commits.nr; i++) {
- uint32_t level = *topo_level_slab_at(ctx->topo_levels, ctx->commits.list[i]);
+ timestamp_t level = *topo_level_slab_at(ctx->topo_levels, ctx->commits.list[i]);
+ timestamp_t corrected_commit_date = commit_graph_data_at(ctx->commits.list[i])->generation;

display_progress(ctx->progress, i + 1);
- if (level != GENERATION_NUMBER_V1_INFINITY &&
+ if (level != GENERATION_NUMBER_INFINITY &&
- level != GENERATION_NUMBER_ZERO)
+ level != GENERATION_NUMBER_ZERO &&
+ corrected_commit_date != GENERATION_NUMBER_INFINITY &&
@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph

for (parent = current->parents; parent; parent = parent->next) {
level = *topo_level_slab_at(ctx->topo_levels, parent->item);
+-
+ corrected_commit_date = commit_graph_data_at(parent->item)->generation;
-
- if (level == GENERATION_NUMBER_V1_INFINITY ||
+ if (level == GENERATION_NUMBER_INFINITY ||
- level == GENERATION_NUMBER_ZERO) {
+ level == GENERATION_NUMBER_ZERO ||
+ corrected_commit_date == GENERATION_NUMBER_INFINITY ||
@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
}

@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
- if (max_level > GENERATION_NUMBER_MAX - 1)
- max_level = GENERATION_NUMBER_MAX - 1;
+ if (max_level > GENERATION_NUMBER_V1_MAX - 1)
+ max_level = GENERATION_NUMBER_V1_MAX - 1;
*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
+
-+ if (current->date > max_corrected_commit_date)
++ 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;
}
}
}
-@@ commit-graph.c: int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
- for (i = 0; i < g->num_commits; i++) {
- struct commit *graph_commit, *odb_commit;
- struct commit_list *graph_parents, *odb_parents;
-- timestamp_t max_generation = 0;
-- timestamp_t generation;
-+ timestamp_t max_corrected_commit_date = 0;
-+ timestamp_t corrected_commit_date;
-
- display_progress(progress, i + 1);
- hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
-@@ commit-graph.c: int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
- oid_to_hex(&graph_parents->item->object.oid),
- oid_to_hex(&odb_parents->item->object.oid));
-
-- generation = commit_graph_generation(graph_parents->item);
-- if (generation > max_generation)
-- max_generation = generation;
-+ corrected_commit_date = commit_graph_generation(graph_parents->item);
-+ if (corrected_commit_date > max_corrected_commit_date)
-+ max_corrected_commit_date = corrected_commit_date;
-
- graph_parents = graph_parents->next;
- odb_parents = odb_parents->next;
@@ commit-graph.c: int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
if (generation_zero == GENERATION_ZERO_EXISTS)
continue;

- /*
-- * If one of our parents has generation GENERATION_NUMBER_MAX, then
-- * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
+- * If one of our parents has generation GENERATION_NUMBER_V1_MAX, then
+- * our generation is also GENERATION_NUMBER_V1_MAX. Decrement to avoid
- * extra logic in the following condition.
- */
-- if (max_generation == GENERATION_NUMBER_MAX)
+- if (max_generation == GENERATION_NUMBER_V1_MAX)
- max_generation--;
-
-- generation = commit_graph_generation(graph_commit);
+ generation = commit_graph_generation(graph_commit);
- if (generation != max_generation + 1)
- graph_report(_("commit-graph generation for commit %s is %u != %u"),
-+ corrected_commit_date = commit_graph_generation(graph_commit);
-+ if (corrected_commit_date < max_corrected_commit_date + 1)
++ if (generation < max_generation + 1)
+ graph_report(_("commit-graph generation for commit %s is %"PRItime" < %"PRItime),
oid_to_hex(&cur_oid),
-- generation,
-- max_generation + 1);
-+ corrected_commit_date,
-+ max_corrected_commit_date + 1);
-
- if (graph_commit->date != odb_commit->date)
- graph_report(_("commit date for commit %s in commit-graph is %"PRItime" != %"PRItime),
+ generation,
+ max_generation + 1);
8: 4e746628ac ! 7: b903efe2ea commit-graph: implement generation data chunk

     @@ Commit message
          between graph versions in a backwards compatible manner.
      
          We are going to introduce a new chunk called Generation Data chunk (or
     -    GDAT). GDAT stores generation number v2 (and any subsequent versions),
     -    whereas CDAT will still store topological level.
     +    GDAT). GDAT stores corrected committer date offsets whereas CDAT will
     +    still store topological level.
      
          Old Git does not understand GDAT chunk and would ignore it, reading
          topological levels from CDAT. New Git can parse GDAT and take advantage
     @@ Commit message
          which forces commit-graph file to be written without generation data
          chunk to emulate a commit-graph file written by old Git.
      
     +    While storing corrected commit date offset instead of the corrected
     +    commit date saves us 4 bytes per commit, it's possible for the offsets
     +    to overflow the 4-bytes allocated. As such overflows are exceedingly
     +    rare, we use the following overflow management scheme:
     +
     +    We introduce a new commit-graph chunk, GENERATION_DATA_OVERFLOW ('GDOV')
     +    to store corrected commit dates for commits with offsets greater than
     +    GENERATION_NUMBER_V2_OFFSET_MAX.
     +
     +    If the offset is greater than GENERATION_NUMBER_V2_OFFSET_MAX, we set
     +    the MSB of the offset and the other bits store the position of corrected
     +    commit date in GDOV chunk, similar to how Extra Edge List is maintained.
     +
     +    We test the overflow-related code with the following repo history:
     +
     +               F - N - U
     +              /         \
     +    U - N - U            N
     +             \          /
     +              N - F - N
     +
     +    Where the commits denoted by U have committer date of zero seconds
     +    since Unix epoch, the commits denoted by N have committer date of
     +    1112354055 (default committer date for the test suite) seconds since
     +    Unix epoch and the commits denoted by F have committer date of
     +    (2 ^ 31 - 2) seconds since Unix epoch.
     +
     +    The largest offset observed is 2 ^ 31, just large enough to overflow.
     +
          [1]: https://lore.kernel.org/git/[email protected]/
      
          Signed-off-by: Abhishek Kumar <[email protected]>
     @@ commit-graph.c: void git_test_write_commit_graph_or_die(void)
       #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_EXTRAEDGES 0x45444745 /* "EDGE" */
       #define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
       #define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
       #define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
      -#define MAX_NUM_CHUNKS 7
     -+#define MAX_NUM_CHUNKS 8
     ++#define MAX_NUM_CHUNKS 9
       
       #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
       
     -@@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size)
     +@@ commit-graph.c: void git_test_write_commit_graph_or_die(void)
     + #define GRAPH_MIN_SIZE (GRAPH_HEADER_SIZE + 4 * GRAPH_CHUNKLOOKUP_WIDTH \
     + 			+ GRAPH_FANOUT_SIZE + the_hash_algo->rawsz)
     + 
     ++#define CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW (1ULL << 31)
     ++
     + /* Remember to update object flag allocation in object.h */
     + #define REACHABLE       (1u<<15)
     + 
     +@@ commit-graph.c: struct commit_graph *parse_commit_graph(struct repository *r,
       				graph->chunk_commit_data = data + chunk_offset;
       			break;
       
     @@ commit-graph.c: struct commit_graph *parse_commit_graph(void *graph_map, size_t
      +			else
      +				graph->chunk_generation_data = data + chunk_offset;
      +			break;
     ++
     ++		case GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW:
     ++			if (graph->chunk_generation_data_overflow)
     ++				chunk_repeated = 1;
     ++			else
     ++				graph->chunk_generation_data_overflow = data + chunk_offset;
     ++			break;
      +
       		case GRAPH_CHUNKID_EXTRAEDGES:
       			if (graph->chunk_extra_edges)
       				chunk_repeated = 1;
     +@@ commit-graph.c: static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
     + {
     + 	const unsigned char *commit_data;
     + 	struct commit_graph_data *graph_data;
     +-	uint32_t lex_index;
     +-	uint64_t date_high, date_low;
     ++	uint32_t lex_index, offset_pos;
     ++	uint64_t date_high, date_low, offset;
     + 
     + 	while (pos < g->num_commits_in_base)
     + 		g = g->base_graph;
      @@ commit-graph.c: static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
       	date_low = get_be32(commit_data + g->hash_len + 12);
       	item->date = (timestamp_t)((date_high << 32) | date_low);
       
      -	graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
     -+	if (g->chunk_generation_data)
     -+		graph_data->generation = item->date +
     -+			(timestamp_t) get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
     -+	else
     ++	if (g->chunk_generation_data) {
     ++		offset = (timestamp_t) get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
     ++
     ++		if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) {
     ++			offset_pos = offset ^ CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW;
     ++			graph_data->generation = get_be64(g->chunk_generation_data_overflow + 8 * offset_pos);
     ++		} else
     ++			graph_data->generation = item->date + offset;
     ++	} else
      +		graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
       
       	if (g->topo_levels)
       		*topo_level_slab_at(g->topo_levels, item) = get_be32(commit_data + g->hash_len + 8) >> 2;
     +@@ commit-graph.c: struct write_commit_graph_context {
     + 	struct packed_oid_list oids;
     + 	struct packed_commit_list commits;
     + 	int num_extra_edges;
     ++	int num_generation_data_overflows;
     + 	unsigned long approx_nr_objects;
     + 	struct progress *progress;
     + 	int progress_done;
      @@ commit-graph.c: struct write_commit_graph_context {
       		 report_progress:1,
       		 split:1,
     @@ commit-graph.c: struct write_commit_graph_context {
      +		 write_generation_data:1;
       
       	struct topo_level_slab *topo_levels;
     - 	const struct split_commit_graph_opts *split_opts;
     + 	const struct commit_graph_opts *opts;
      @@ commit-graph.c: static int write_graph_chunk_data(struct hashfile *f,
       	return 0;
       }
     @@ commit-graph.c: static int write_graph_chunk_data(struct hashfile *f,
      +static int write_graph_chunk_generation_data(struct hashfile *f,
      +					      struct write_commit_graph_context *ctx)
      +{
     -+	int i;
     ++	int i, num_generation_data_overflows = 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;
      +		display_progress(ctx->progress, ++ctx->progress_cnt);
      +
     -+		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
     -+			offset = GENERATION_NUMBER_V2_OFFSET_MAX;
     ++		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
     ++			offset = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW | num_generation_data_overflows;
     ++			num_generation_data_overflows++;
     ++		}
     ++
      +		hashwrite_be32(f, offset);
      +	}
      +
      +	return 0;
      +}
     ++
     ++static int write_graph_chunk_generation_data_overflow(struct hashfile *f,
     ++						       struct write_commit_graph_context *ctx)
     ++{
     ++	int i;
     ++	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;
     ++		display_progress(ctx->progress, ++ctx->progress_cnt);
     ++
     ++		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
     ++			hashwrite_be32(f, offset >> 32);
     ++			hashwrite_be32(f, (uint32_t) offset);
     ++		}
     ++	}
     ++
     ++	return 0;
     ++}
      +
       static int write_graph_chunk_extra_edges(struct hashfile *f,
     --					 struct write_commit_graph_context *ctx)
     -+					  struct write_commit_graph_context *ctx)
     + 					 struct write_commit_graph_context *ctx)
       {
     - 	struct commit **list = ctx->commits.list;
     - 	struct commit **last = ctx->commits.list + ctx->commits.nr;
     +@@ commit-graph.c: 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++;
     + 			}
     + 		}
     + 	}
      @@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_context *ctx)
       	chunks[2].id = GRAPH_CHUNKID_DATA;
       	chunks[2].size = (hashsz + 16) * ctx->commits.nr;
     @@ commit-graph.c: static int write_commit_graph_file(struct write_commit_graph_con
      +		chunks[num_chunks].size = sizeof(uint32_t) * ctx->commits.nr;
      +		chunks[num_chunks].write_fn = write_graph_chunk_generation_data;
      +		num_chunks++;
     ++	}
     ++	if (ctx->num_generation_data_overflows) {
     ++		chunks[num_chunks].id = GRAPH_CHUNKID_GENERATION_DATA_OVERFLOW;
     ++		chunks[num_chunks].size = sizeof(timestamp_t) * ctx->num_generation_data_overflows;
     ++		chunks[num_chunks].write_fn = write_graph_chunk_generation_data_overflow;
     ++		num_chunks++;
      +	}
       	if (ctx->num_extra_edges) {
       		chunks[num_chunks].id = GRAPH_CHUNKID_EXTRAEDGES;
       		chunks[num_chunks].size = 4 * ctx->num_extra_edges;
      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
       	ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
     - 	ctx->split_opts = split_opts;
     + 	ctx->opts = opts;
       	ctx->total_bloom_filter_data_size = 0;
      +	ctx->write_generation_data = 1;
     ++	ctx->num_generation_data_overflows = 0;
       
     - 	if (flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS)
     - 		ctx->changed_paths = 1;
     + 	bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
     + 						      bloom_settings.bits_per_entry);
      
       ## commit-graph.h ##
      @@
     @@ commit-graph.h: struct commit_graph {
       	const unsigned char *chunk_oid_lookup;
       	const unsigned char *chunk_commit_data;
      +	const unsigned char *chunk_generation_data;
     ++	const unsigned char *chunk_generation_data_overflow;
       	const unsigned char *chunk_extra_edges;
       	const unsigned char *chunk_base_graphs;
       	const unsigned char *chunk_bloom_indexes;
      
     + ## commit.h ##
     +@@
     + #define GENERATION_NUMBER_INFINITY ((1ULL << 63) - 1)
     + #define GENERATION_NUMBER_V1_MAX 0x3FFFFFFF
     + #define GENERATION_NUMBER_ZERO 0
     ++#define GENERATION_NUMBER_V2_OFFSET_MAX ((1ULL << 31) - 1)
     + 
     + struct commit_list {
     + 	struct commit *item;
     +
       ## t/README ##
      @@ t/README: GIT_TEST_COMMIT_GRAPH=<boolean>, when true, forces the commit-graph to
       be written after every 'git commit' command, and overrides the
     @@ t/helper/test-read-graph.c: int cmd__read_graph(int argc, const char **argv)
       		printf(" commit_metadata");
      +	if (graph->chunk_generation_data)
      +		printf(" generation_data");
     ++	if (graph->chunk_generation_data_overflow)
     ++		printf(" generation_data_overflow");
       	if (graph->chunk_extra_edges)
       		printf(" extra_edges");
       	if (graph->chunk_bloom_indexes)
      
       ## t/t4216-log-bloom.sh ##
      @@ t/t4216-log-bloom.sh: test_expect_success 'setup test - repo, commits, commit graph, log outputs' '
     - 	git commit-graph write --reachable --changed-paths
       '
     + 
       graph_read_expect () {
      -	NUM_CHUNKS=5
      +	NUM_CHUNKS=6
       	cat >expect <<- EOF
     - 	header: 43475048 1 1 $NUM_CHUNKS 0
     + 	header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0
       	num_commits: $1
      -	chunks: oid_fanout oid_lookup commit_metadata bloom_indexes bloom_data
      +	chunks: oid_fanout oid_lookup commit_metadata generation_data bloom_indexes bloom_data
     @@ t/t5318-commit-graph.sh: test_expect_success 'write graph in bare repo' '
       '
       
       graph_git_behavior 'bare repo with graph, commit 8 vs merge 1' bare commits/8 merge/1
     -@@ t/t5318-commit-graph.sh: test_expect_success 'replace-objects invalidates commit-graph' '
     +@@ t/t5318-commit-graph.sh: test_expect_success 'warn on improper hash version' '
       
       test_expect_success 'git commit-graph verify' '
       	cd "$TRASH_DIRECTORY/full" &&
     @@ t/t5318-commit-graph.sh: test_expect_success 'replace-objects invalidates commit
       '
       
       NUM_COMMITS=9
     +@@ t/t5318-commit-graph.sh: test_expect_success 'corrupt commit-graph write (missing tree)' '
     + 	)
     + '
     + 
     ++test_commit_with_date() {
     ++  file="$1.t" &&
     ++  echo "$1" >"$file" &&
     ++  git add "$file" &&
     ++  GIT_COMMITTER_DATE="$2" GIT_AUTHOR_DATE="$2" git commit -m "$1"
     ++  git tag "$1"
     ++}
     ++
     ++test_expect_success 'overflow corrected commit date offset' '
     ++	objdir=".git/objects" &&
     ++	UNIX_EPOCH_ZERO="1970-01-01 00:00 +0000" &&
     ++	FUTURE_DATE="@2147483646 +0000" &&
     ++	test_oid_cache <<-EOF &&
     ++	oid_version sha1:1
     ++	oid_version sha256:2
     ++	EOF
     ++	cd "$TRASH_DIRECTORY" &&
     ++	mkdir repo &&
     ++	cd repo &&
     ++	git init &&
     ++	test_commit_with_date 1 "$UNIX_EPOCH_ZERO" &&
     ++	test_commit 2 &&
     ++	test_commit_with_date 3 "$UNIX_EPOCH_ZERO" &&
     ++	git commit-graph write --reachable &&
     ++	graph_read_expect 3 generation_data &&
     ++	test_commit_with_date 4 "$FUTURE_DATE" &&
     ++	test_commit 5 &&
     ++	test_commit_with_date 6 "$UNIX_EPOCH_ZERO" &&
     ++	git branch left &&
     ++	git reset --hard 3 &&
     ++	test_commit 7 &&
     ++	test_commit_with_date 8 "$FUTURE_DATE" &&
     ++	test_commit 9 &&
     ++	git branch right &&
     ++	git reset --hard 3 &&
     ++	git merge left right &&
     ++	git commit-graph write --reachable &&
     ++	graph_read_expect 10 "generation_data generation_data_overflow" &&
     ++	git commit-graph verify
     ++'
     ++
     ++graph_git_behavior 'overflow corrected commit date offset' repo left right
     ++
     + test_done
      
       ## t/t5324-split-commit-graph.sh ##
      @@ t/t5324-split-commit-graph.sh: test_expect_success 'setup repo' '
     @@ t/t5324-split-commit-graph.sh: test_expect_success 'setup repo' '
      -	base sha256:1496
      +	base sha1:1408
      +	base sha256:1528
     - 	EOM
     - '
       
     + 	oid_version sha1:1
     + 	oid_version sha256:2
      @@ t/t5324-split-commit-graph.sh: graph_read_expect() {
       		NUM_BASE=$2
       	fi
       	cat >expect <<- EOF
     --	header: 43475048 1 1 3 $NUM_BASE
     -+	header: 43475048 1 1 4 $NUM_BASE
     +-	header: 43475048 1 $(test_oid oid_version) 3 $NUM_BASE
     ++	header: 43475048 1 $(test_oid oid_version) 4 $NUM_BASE
       	num_commits: $1
      -	chunks: oid_fanout oid_lookup commit_metadata
      +	chunks: oid_fanout oid_lookup commit_metadata generation_data
     @@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases:miss' '
      +	test_all_modes in_merge_bases
       '
       
     + test_expect_success 'in_merge_bases_many:hit' '
     +@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:hit' '
     + 	X:commit-5-7
     + 	EOF
     + 	echo "in_merge_bases_many(A,X):1" >expect &&
     +-	test_three_modes in_merge_bases_many
     ++	test_all_modes in_merge_bases_many
     + '
     + 
     + test_expect_success 'in_merge_bases_many:miss' '
     +@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:miss' '
     + 	X:commit-8-6
     + 	EOF
     + 	echo "in_merge_bases_many(A,X):0" >expect &&
     +-	test_three_modes in_merge_bases_many
     ++	test_all_modes in_merge_bases_many
     + '
     + 
     + test_expect_success 'in_merge_bases_many:miss-heuristic' '
     +@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:miss-heuristic' '
     + 	X:commit-6-6
     + 	EOF
     + 	echo "in_merge_bases_many(A,X):0" >expect &&
     +-	test_three_modes in_merge_bases_many
     ++	test_all_modes in_merge_bases_many
     + '
     + 
       test_expect_success 'is_descendant_of:hit' '
      @@ t/t6600-test-reach.sh: test_expect_success 'is_descendant_of:hit' '
       	X:commit-1-1
  9:  5a147a9704 !  8:  8ec119edc6 commit-graph: use generation v2 only if entire chain does
     @@ Commit message
          commits in the lower layer before allowing the topo-order queue to write
          anything to output (depending on the size of the upper layer).
      
     +    When writing the new layer in split commit-graph, we write a GDAT chunk
     +    only if the topmost layer has a GDAT chunk. This guarantees that if a
     +    layer has GDAT chunk, all lower layers must have a GDAT chunk as well.
     +
     +    Rewriting layers follows similar approach: if the topmost layer below
     +    the set of layers being rewritten (in the split commit-graph chain)
     +    exists, and it does not contain GDAT chunk, then the result of rewrite
     +    does not have GDAT chunks either.
     +
          Signed-off-by: Derrick Stolee <[email protected]>
          Signed-off-by: Abhishek Kumar <[email protected]>
      
     @@ commit-graph.c: static struct commit_graph *load_commit_graph_chain(struct repos
       	return graph_chain;
       }
       
     -+static void validate_mixed_generation_chain(struct repository *r)
     ++static void validate_mixed_generation_chain(struct commit_graph *g)
      +{
     -+	struct commit_graph *g = r->objects->commit_graph;
     -+	int read_generation_data = 1;
     ++	int read_generation_data;
      +
     -+	while (g) {
     -+		if (!g->chunk_generation_data) {
     -+			read_generation_data = 0;
     -+			break;
     -+		}
     -+		g = g->base_graph;
     -+	}
     ++	if (!g)
     ++		return;
      +
     -+	g = r->objects->commit_graph;
     ++	read_generation_data = !!g->chunk_generation_data;
      +
      +	while (g) {
      +		g->read_generation_data = read_generation_data;
     @@ commit-graph.c: struct commit_graph *read_commit_graph_one(struct repository *r,
       	if (!g)
       		g = load_commit_graph_chain(r, odb);
       
     -+	validate_mixed_generation_chain(r);
     ++	validate_mixed_generation_chain(g);
      +
       	return g;
       }
     @@ commit-graph.c: static void fill_commit_graph_info(struct commit *item, struct c
       	date_low = get_be32(commit_data + g->hash_len + 12);
       	item->date = (timestamp_t)((date_high << 32) | date_low);
       
     --	if (g->chunk_generation_data)
     -+	if (g->chunk_generation_data && g->read_generation_data)
     - 		graph_data->generation = item->date +
     - 			(timestamp_t) get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
     - 	else
     -@@ commit-graph.c: void load_commit_graph_info(struct repository *r, struct commit *item)
     - 	uint32_t pos;
     - 	if (!prepare_commit_graph(r))
     - 		return;
     +-	if (g->chunk_generation_data) {
     ++	if (g->chunk_generation_data && g->read_generation_data) {
     + 		offset = (timestamp_t) get_be32(g->chunk_generation_data + sizeof(uint32_t) * lex_index);
     + 
     + 		if (offset & CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW) {
     +@@ commit-graph.c: static void split_graph_merge_strategy(struct write_commit_graph_context *ctx)
     + 		}
     + 	}
     + 
     ++	if (!ctx->write_generation_data && g->chunk_generation_data)
     ++		ctx->write_generation_data = 1;
      +
     - 	if (find_commit_in_graph(item, r->objects->commit_graph, &pos))
     - 		fill_commit_graph_info(item, r->objects->commit_graph, pos);
     - }
     + 	if (flags != COMMIT_GRAPH_SPLIT_REPLACE)
     + 		ctx->new_base_graph = g;
     + 	else if (ctx->num_commit_graphs_after != 1)
     +@@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
     + 		struct commit_graph *g = ctx->r->objects->commit_graph;
     + 
     + 		while (g) {
     ++			g->read_generation_data = 1;
     + 			g->topo_levels = &topo_levels;
     + 			g = g->base_graph;
     + 		}
      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
       
       		g = ctx->r->objects->commit_graph;
     @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
       			g = g->base_graph;
      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
       
     - 		if (ctx->split_opts)
     - 			replace = ctx->split_opts->flags & COMMIT_GRAPH_SPLIT_REPLACE;
     + 		if (ctx->opts)
     + 			replace = ctx->opts->split_flags & COMMIT_GRAPH_SPLIT_REPLACE;
      +
      +		if (replace)
      +			ctx->write_generation_data = 1;
     @@ commit-graph.h: struct commit_graph {
       	struct object_directory *odb;
       
       	uint32_t num_commits_in_base;
     -+	uint32_t read_generation_data;
     ++	unsigned int read_generation_data;
       	struct commit_graph *base_graph;
       
       	const uint32_t *chunk_oid_fanout;
      
       ## t/t5324-split-commit-graph.sh ##
     -@@ t/t5324-split-commit-graph.sh: done <<\EOF
     - 0600 -r--------
     - EOF
     +@@ t/t5324-split-commit-graph.sh: test_expect_success '--split=replace with partial Bloom data' '
     + 	verify_chain_files_exist $graphdir
     + '
       
      +test_expect_success 'setup repo for mixed generation commit-graph-chain' '
      +	mkdir mixed &&
      +	graphdir=".git/objects/info/commit-graphs" &&
     ++	test_oid_cache <<-EOM &&
     ++	oid_version sha1:1
     ++	oid_version sha256:2
     ++	EOM
      +	cd "$TRASH_DIRECTORY/mixed" &&
      +	git init &&
      +	git config core.commitGraph true &&
     @@ t/t5324-split-commit-graph.sh: done <<\EOF
      +	GIT_TEST_COMMIT_GRAPH_NO_GDAT=1 git commit-graph write --reachable --split=no-merge &&
      +	test-tool read-graph >output &&
      +	cat >expect <<-EOF &&
     -+	header: 43475048 1 1 4 1
     ++	header: 43475048 1 $(test_oid oid_version) 4 1
      +	num_commits: 2
      +	chunks: oid_fanout oid_lookup commit_metadata
      +	EOF
     @@ t/t5324-split-commit-graph.sh: done <<\EOF
      +	git commit-graph write --reachable --split=no-merge &&
      +	test-tool read-graph >output &&
      +	cat >expect <<-EOF &&
     -+	header: 43475048 1 1 4 2
     ++	header: 43475048 1 $(test_oid oid_version) 4 2
      +	num_commits: 3
      +	chunks: oid_fanout oid_lookup commit_metadata
      +	EOF
     @@ t/t5324-split-commit-graph.sh: done <<\EOF
      +	graph_read_expect 15 &&
      +	git commit-graph verify
      +'
     ++
     ++test_expect_success 'add one commit, write a tip graph' '
     ++	cd "$TRASH_DIRECTORY/mixed" &&
     ++	test_commit 11 &&
     ++	git branch commits/11 &&
     ++	git commit-graph write --reachable --split &&
     ++	test_path_is_missing $infodir/commit-graph &&
     ++	test_path_is_file $graphdir/commit-graph-chain &&
     ++	ls $graphdir/graph-*.graph >graph-files &&
     ++	test_line_count = 2 graph-files &&
     ++	verify_chain_files_exist $graphdir
     ++'
      +
       test_done

10: 439adc1718 ! 9: bb9b02af32 commit-reach: use corrected commit dates in paint_down_to_common()
@@ Commit message
With corrected commit dates implemented, we no longer have to rely on commit date as a heuristic in paint_down_to_common().

- t6024-recursive-merge setups a unique repository where all commits have
- the same committer date without well-defined merge-base. As this has
- already caused problems (as noted in 859fdc0 (commit-graph: define
- GIT_TEST_COMMIT_GRAPH, 2018-08-29)), we disable commit graph within the
- test script.
+ While using corrected commit dates Git walks nearly the same number of
+ commits as commit date, the process is slower as for each comparision we
+ have to access a commit-slab (for corrected committer date) instead of
+ accessing struct member (for committer date).
+
+ For example, the command git merge-base v4.8 v4.9 on the linux
+ repository walks 167468 commits, taking 0.135s for committer date and
+ 167496 commits, taking 0.157s for corrected committer date respectively.
+
+ t6404-recursive-merge setups a unique repository where all commits have
+ the same committer date without well-defined merge-base.
+
+ While running tests with GIT_TEST_COMMIT_GRAPH unset, we use committer
+ date as a heuristic in paint_down_to_common(). 6404.1 'combined merge
+ conflicts' merges commits in the order:
+ - Merge C with B to form a intermediate commit.
+ - Merge the intermediate commit with A.
+
+ With GIT_TEST_COMMIT_GRAPH=1, we write a commit-graph and subsequently
+ use the corrected committer date, which changes the order in which
+ commits are merged:
+ - Merge A with B to form a intermediate commit.
+ - Merge the intermediate commit with C.
+
+ While resulting repositories are equivalent, 6404.4 'virtual trees were
+ processed' fails with GIT_TEST_COMMIT_GRAPH=1 as we are selecting
+ different merge-bases and thus have different object ids for the
+ intermediate commits.
+
+ As this has already causes problems (as noted in 859fdc0 (commit-graph:
+ define GIT_TEST_COMMIT_GRAPH, 2018-08-29)), we disable commit graph
+ within t6404-recursive-merge.

@@ commit-graph.c: int generation_numbers_enabled(struct repository *r)
+ if (!g->num_commits)
+ return 0;
+
-+ return !!g->chunk_generation_data;
++ return g->read_generation_data;
+}
+
- static void close_commit_graph_one(struct commit_graph *g)
+ struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r) {
- if (!g)
+ struct commit_graph *g = r->objects->commit_graph;

## commit-graph.h ##
-@@ commit-graph.h: struct commit_graph *parse_commit_graph(void *graph_map, size_t graph_size); +@@ commit-graph.h: struct commit_graph *read_commit_graph_one(struct repository *r,
+ struct commit_graph *parse_commit_graph(struct repository *r,
+ void *graph_map, size_t graph_size);
+
++struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r); ++
+ /*
+ * Return 1 if and only if the repository has a commit-graph
+ * file and generation numbers are computed in that file.
*/
int generation_numbers_enabled(struct repository *r);

+-struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r);
+/*
+ * Return 1 if and only if the repository has a commit-graph
+ * file and generation data chunk has been written for the file.
+ */
+int corrected_commit_dates_enabled(struct repository *r);
-+
+
enum commit_graph_write_flags {
COMMIT_GRAPH_WRITE_APPEND = (1 << 0),
- COMMIT_GRAPH_WRITE_PROGRESS = (1 << 1),

## commit-reach.c ##
@@ commit-reach.c: static struct commit_list *paint_down_to_common(struct repository *r,
@@ commit-reach.c: static struct commit_list *paint_down_to_common(struct repositor

one->object.flags |= PARENT1;

- ## t/t6024-recursive-merge.sh ##
-@@ t/t6024-recursive-merge.sh: GIT_COMMITTER_DATE="2006-12-12 23:28:00 +0100"
+ ## t/t6404-recursive-merge.sh ##
+@@ t/t6404-recursive-merge.sh: GIT_COMMITTER_DATE="2006-12-12 23:28:00 +0100"
export GIT_COMMITTER_DATE

test_expect_success 'setup tests' '
@@ t/t6024-recursive-merge.sh: GIT_COMMITTER_DATE="2006-12-12 23:28:00 +0100"
echo 1 >a1 &&
git add a1 &&
GIT_AUTHOR_DATE="2006-12-12 23:00:00" git commit -m 1 a1 &&
-@@ t/t6024-recursive-merge.sh: test_expect_success 'setup tests' ' +@@ t/t6404-recursive-merge.sh: test_expect_success 'setup tests' '
'

test_expect_success 'combined merge conflicts' '
@@ t/t6024-recursive-merge.sh: test_expect_success 'setup tests' '
'

test_expect_success 'result contains a conflict' '
+@@ t/t6404-recursive-merge.sh: test_expect_success 'result contains a conflict' '
+ '
+
+ test_expect_success 'virtual trees were processed' '
++ # TODO: fragile test, relies on ambigious merge-base resolution
+ git ls-files --stage >out &&
+
+ cat >expect <<-EOF &&
11: f6f91af305 ! 10: 9ada43967d doc: add corrected commit date info
@@ Documentation/technical/commit-graph-format.txt: Git commit graph format
- The root tree OID.

@@ Documentation/technical/commit-graph-format.txt: 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 generation number of the commit and
++ * 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
+ 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.

-+ Generation Data (ID: {'G', 'D', 'A', 'T' }) (N * 4 bytes) [Optional] ++ Generation Data (ID: {'G', 'D', 'A', 'T' }) (N * 4 bytes)
+ * This list of 4-byte values store corrected commit date offsets for the
+ commits, arranged in the same order as commit data chunk.
-+ * This list can be later modified to store future generation number related
-+ data.
++ * If the corrected commit date offset cannot be stored within 31 bits,
++ the value has its most-significant bit on and the other bits store
++ the position of corrected commit date into the Generation Data Overflow
++ chunk.
++
++ Generation Data Overflow (ID: {'G', 'D', 'O', 'V' }) [Optional]
++ * This list of 8-byte values stores the corrected commit dates for commits
++ with corrected commit date offsets that cannot be stored within 31 bits.
+
Extra Edge List (ID: {'E', 'D', 'G', 'E'}) [Optional]
This list of 4-byte values store the second through nth parents for
@@ Documentation/technical/commit-graph.txt: A consumer may load the following info

-Define the "generation number" of a commit recursively as follows:
+There are two definitions of generation number:
-+1. Corrected committer dates
-+2. Topological levels
-+
++1. Corrected committer dates (generation number v2)
++2. Topological levels (generation nummber v1)
+
+- * A commit with no parents (a root commit) has generation number one.
+Define "corrected committer date" of a commit recursively as follows:
-+
+
+- * A commit with at least one parent has generation number one more than
+- the largest generation number among its parents.
+ * A commit with no parents (a root commit) has corrected committer date
+ equal to its committer date.
-+
+
+-Equivalently, the generation number of a commit A is one more than the
+ * A commit with at least one parent has corrected committer date equal to
+ the maximum of its commiter date and one more than the largest corrected
+ committer date among its parents.
+
++ * As a special case, a root commit with timestamp zero has corrected commit
++ date of 1, to be able to distinguish it from GENERATION_NUMBER_ZERO
++ (that is, an uncomputed corrected commit date).
++
+Define the "topological level" of a commit recursively as follows:
-
- * A commit with no parents (a root commit) has generation number one. -
-- * A commit with at least one parent has generation number one more than
-- the largest generation number among its parents.
++
++ * A commit with no parents (a root commit) has topological level of one. ++
+ * A commit with at least one parent has topological level one more than
+ the largest topological level among its parents.
-
--Equivalently, the generation number of a commit A is one more than the ++
+Equivalently, the topological level of a commit A is one more than the
length of a longest path from A to a root commit. The recursive definition is easier to use for computation and observing the following property:

+@@ Documentation/technical/commit-graph.txt: is easier to use for computation and observing the following property:
+ generation numbers, then we always expand the boundary commit with highest
+ generation number and can easily detect the stopping condition.
+
++The properties applies to both versions of generation number, that is both
++corrected committer dates and topological levels.
++
+ This property can be used to significantly reduce the time it takes to
+ walk commits and determine topological relationships. Without generation
+ numbers, the general heuristic is the following:
@@ Documentation/technical/commit-graph.txt: numbers, the general heuristic is the following:
If A and B are commits with commit time X and Y, respectively, and
X < Y, then A _probably_ cannot reach B.

-This heuristic is currently used whenever the computation is allowed to
--violate topological relationships due to clock skew (such as "git log"
--with default order), but is not used when the topological order is
--required (such as merge base calculations, "git log --graph").
--
- In practice, we expect some commits to be created recently and not stored
- in the commit graph. We can treat these commits as having "infinite"
++In absence of corrected commit dates (for example, old versions of Git or
++mixed generation graph chains),
++this heuristic is currently used whenever the computation is allowed to
+ violate topological relationships due to clock skew (such as "git log"
+ with default order), but is not used when the topological order is
+ required (such as merge base calculations, "git log --graph").
+@@ Documentation/technical/commit-graph.txt: in the commit graph. We can treat these commits as having "infinite"
generation number and walk until reaching commits with known generation
number.

@@ Documentation/technical/commit-graph.txt: fully-computed generation numbers. Usi
with generation number *_INFINITY or *_ZERO is valuable.

-We use the macro GENERATION_NUMBER_MAX = 0x3FFFFFFF to for commits whose
--generation numbers are computed to be at least this value. We limit at
--this value since it is the largest value that can be stored in the
--commit-graph file using the 30 bits available to generation numbers. This
--presents another case where a commit can have generation number equal to
--that of a parent.
-+We use the macro GENERATION_NUMBER_MAX for commits whose generation numbers
-+are computed to be at least this value. We limit at this value since it is
-+the largest value that can be stored in the commit-graph file using the
-+available to generation numbers. This presents another case where a
-+commit can have generation number equal to that of a parent.
-
- Design Details
- --------------
++We use the macro GENERATION_NUMBER_MAX for commits whose
+ generation numbers are computed to be at least this value. We limit at
+ this value since it is the largest value that can be stored in the
+ commit-graph file using the 30 bits available to generation numbers. This
@@ Documentation/technical/commit-graph.txt: The merge strategy values (2 for the size multiple, 64,000 for the maximum
number of commits) could be extracted into config settings for full
flexibility.

-+We also merge commit-graph chains when we try to write a commit graph with -+two different generation number definitions as they cannot be compared directly. -+We overwrite the existing chain and create a commit-graph with the newer or more -+efficient defintion. For example, overwriting topological levels commit graph -+chain to create a corrected commit dates commit graph chain.
++## Handling Mixed Generation Number Chains
++
++With the introduction of generation number v2 and generation data chunk, the ++following scenario is possible:
++
++1. "New" Git writes a commit-graph with the corrected commit dates. ++2. "Old" Git writes a split commit-graph on top without corrected commit dates. ++
++A naive approach of using the newest available generation number from ++each layer would lead to violated expectations: the lower layer would ++use corrected commit dates which are much larger than the topological ++levels of the higher layer. For this reason, Git inspects each layer to ++see if any layer is missing corrected commit dates. In such a case, Git ++only uses topological level
++
++When writing a new layer in split commit-graph, we write corrected commit ++dates if the topmost layer has corrected commit dates written. This ++guarantees that if a layer has corrected commit dates, all lower layers ++must have corrected commit dates as well.
++
++When merging layers, we do not consider whether the merged layers had corrected ++commit dates. Instead, the new layer will have corrected commit dates if and ++only if all existing layers below the new layer have corrected commit dates.
+
## Deleting graph-{hash} files

gitgitgadget

From: Abhishek Kumar <[email protected]>

commit_gen_cmp is used when writing a commit-graph to sort commits in generation order before computing Bloom filters. Since c49c82aa (commit:
move members graph_pos, generation to a slab, 2020-06-17) made it so that 'commit_graph_generation()' returns 'GENERATION_NUMBER_INFINITY' during writing, we cannot call it within this function. Instead, access the generation number directly through the slab (i.e., by calling 'commit_graph_data_at(c)->generation') in order to access it while writing.

While measuring performance with git commit-graph write --reachable --changed-paths on the linux repository led to around 1m40s for both HEAD and master (and could be due to fault in my measurements), it is still the "right" thing to do.

---
 commit-graph.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

index cb042bdba8..94503e584b 100644
@@ -144,8 +144,8 @@ static int commit_gen_cmp(const void *va, const void *vb)
 	const struct commit *a = *(const struct commit **)va;
 	const struct commit *b = *(const struct commit **)vb;
 
-	uint32_t generation_a = commit_graph_generation(a);
-	uint32_t generation_b = commit_graph_generation(b);
+	uint32_t generation_a = commit_graph_data_at(a)->generation;
+	uint32_t generation_b = commit_graph_data_at(b)->generation;
 	/* lower generation commits first */
 	if (generation_a < generation_b)
 		return -1;

gitgitgadget

This description is all right, but I think it can be made more clear:

When running git commit-graph write --reachable --changed-paths to compute Bloom filters for changed paths, commits are first sorted by generation number using 'commit_gen_cmp()'. Commits with similar generation are more likely to have many trees in common, making the diff faster, see 3d112755.

However, since c49c82aa (commit: move members graph_pos, generation to a slab, 2020-06-17) made it so that 'commit_graph_generation()' returns 'GENERATION_NUMBER_INFINITY' during writing, we cannot call it within this function. Instead, access the generation number directly through the slab (i.e., by calling 'commit_graph_data_at(c)->generation') in order to access it while writing.

Or something like that.

We should also add an explanation why avoiding getter is safe here, perhaps adding the following line to the second paragraph:

It is safe to do because 'commit_gen_cmp()' from commit-graph.c is static and used only when writing Bloom filters, and because writing changed-paths filters is done after computing generation numbers (if necessary).

Or something like that.

I had to read the above paragraph several times to understand it, possibly because I have expected here to be a fix for a performance regression. The commit message for 3d112755 (commit-graph: examine commits by generation number) describes reduction of computation time from 3m00s to 1m37s. So I would expect performance with HEAD (i.e. before those changes) to be around 3m, not the same before and after changes being around 1m40s.

Can anyone recheck this before-and-after benchmark, please?

Anyway, it might be more clear to write it as the following:

On the Linux kernel repository, this patch didn't reduce the computation time for 'git commit-graph write --reachable --changed-paths', which is around 1m40s both before and after this change. This could be a fault in my measurements; it is still the "right" thing to do.

Or something like that.

Anyway, it is nice and clear change.

Jakub Narębski

My hunch is that our heuristic to fall back to the commits 'date' value is saving us here. commit_gen_cmp() first compares the generation numbers, breaking ties by 'date' as a heuristic. But since all generation number queries return GENERATION_NUMBER_INFINITY during writing, we're relying on our heuristic entirely.

I haven't looked much further than that, other than to see that I could get about a ~4sec speed-up with this patch as compared to v2.29.1 in the computing Bloom filters region on the kernel.

Assuming that we are in fact being saved by the "date" heuristic, I'd probably write the following commit message instead:

Before computing Bloom filters, the commit-graph machinery uses commit_gen_cmp to sort commits by generation order for improved diff performance. 3d11275505 (commit-graph: examine commits by generation number, 2020-03-30) claims that this sort can reduce the time spent to compute Bloom filters by nearly half.

But since c49c82aa4c (commit: move members graph_pos, generation to a slab, 2020-06-17), this optimization is broken, since asking for 'commit_graph_generation()' directly returns GENERATION_NUMBER_INFINITY while writing.

Not all hope is lost, though: 'commit_graph_generation()' falls back to comparing commits by their date when they have equal generation number, and so since c49c82aa4c is purely a date comparison function. This heuristic is good enough that we don't seem to loose appreciable performance while computing Bloom filters. [Benchmark that we loose about ~4sec before/after c49c82aa4c9...]

So, avoid the uesless 'commit_graph_generation()' while writing by instead accessing the slab directly. This returns the newly-computed generation numbers, and allows us to avoid the heuristic by directly comparing generation numbers.

Thanks,
Taylor

Thanks for benchmarking it. I wasn't sure if I am testing it correctly or the patch made no difference.

That's a lot better, will change.

From: Abhishek Kumar <[email protected]>

In indegree_walk_step(), we add unvisited parents to the indegree queue. However, parents are not guaranteed to be parsed. As the indegree queue sorts by generation number, let's parse parents before inserting them to ensure the correct priority order.

---
 revision.c | 3 +++
 1 file changed, 3 insertions(+)

index aa62212040..c97abcdde1 100644
@@ -3381,6 +3381,9 @@ static void indegree_walk_step(struct rev_info *revs)
 		struct commit *parent = p->item;
 		int *pi = indegree_slab_at(&info->indegree, parent);
 
+		if (repo_parse_commit_gently(revs->repo, parent, 1) < 0)
+			return;
+
 		if (*pi)
 			(*pi)++;
 		else

gitgitgadget

All right, we need to ensure the parent commit is parsed to know its generation number, to insert in into priority queue in a correct order.

Looks good.

Jakub Narębski

From: Abhishek Kumar <[email protected]>

Both fill_commit_graph_info() and fill_commit_in_graph() parse information present in commit data chunk. Let's simplify the implementation by calling fill_commit_graph_info() within fill_commit_in_graph().

fill_commit_graph_info() used to not load committer data from commit data chunk. However, with the corrected committer date, we have to load committer date to calculate generation number value.

e51217e15 (t5000: test tar files that overflow ustar headers, 30-06-2016) introduced a test 'generate tar with future mtime' that creates a commit with committer date of (2 ^ 36 + 1) seconds since EPOCH. The CDAT chunk provides 34-bits for storing committer date, thus committer time overflows into generation number (within CDAT chunk) and has undefined behavior.

The test used to pass as fill_commit_graph_info() would not set struct member date of struct commit and loads committer date from the object database, generating a tar file with the expected mtime.

However, with corrected commit date, we will load the committer date from CDAT chunk (truncated to lower 34-bits to populate the generation number. Thus, Git sets date and generates tar file with the truncated mtime.

The ustar format (the header format used by most modern tar programs) only has room for 11 (or 12, depending om some implementations) octal digits for the size and mtime of each files.

Thus, setting a timestamp of 2 ^ 33 + 1 would overflow the 11-octal digit implementations while still fitting into commit data chunk.

Since we want to test 12-octal digit implementations of ustar as well, let's modify the existing test to no longer use commit-graph file.

---
 commit-graph.c      | 27 ++++++++++-----------------
 t/t5000-tar-tree.sh | 20 +++++++++++++++++++-
 2 files changed, 29 insertions(+), 18 deletions(-)

index 94503e584b..e8362e144e 100644
@@ -749,15 +749,24 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 	const unsigned char *commit_data;
 	struct commit_graph_data *graph_data;
 	uint32_t lex_index;
+	uint64_t date_high, date_low;
 
 	while (pos < g->num_commits_in_base)
 		g = g->base_graph;
 
+	if (pos >= g->num_commits + g->num_commits_in_base)
+		die(_("invalid commit position. commit-graph is likely corrupt"));
+
 	lex_index = pos - g->num_commits_in_base;
 	commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
 
 	graph_data = commit_graph_data_at(item);
 	graph_data->graph_pos = pos;
+
+	date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
+	date_low = get_be32(commit_data + g->hash_len + 12);
+	item->date = (timestamp_t)((date_high << 32) | date_low);
+
 	graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 }
 

@@ -772,38 +781,22 @@ static int fill_commit_in_graph(struct repository *r,
 {
 	uint32_t edge_value;
 	uint32_t *parent_data_ptr;
-	uint64_t date_low, date_high;
 	struct commit_list **pptr;
-	struct commit_graph_data *graph_data;
 	const unsigned char *commit_data;
 	uint32_t lex_index;
 
 	while (pos < g->num_commits_in_base)
 		g = g->base_graph;
 
-	if (pos >= g->num_commits + g->num_commits_in_base)
-		die(_("invalid commit position. commit-graph is likely corrupt"));
+	fill_commit_graph_info(item, g, pos);
 
-	/*
-	 * Store the "full" position, but then use the
-	 * "local" position for the rest of the calculation.
-	 */
-	graph_data = commit_graph_data_at(item);
-	graph_data->graph_pos = pos;
 	lex_index = pos - g->num_commits_in_base;
-
 	commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
 
 	item->object.parsed = 1;
 
 	set_commit_tree(item, NULL);
 
-	date_high = get_be32(commit_data + g->hash_len + 8) & 0x3;
-	date_low = get_be32(commit_data + g->hash_len + 12);
-	item->date = (timestamp_t)((date_high << 32) | date_low);
-
-	graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
-
 	pptr = &item->parents;
 
 	edge_value = get_be32(commit_data + g->hash_len);

index 3ebb0d3b65..8f41cdc509 100755
@@ -431,11 +431,29 @@ test_expect_success TAR_HUGE,LONG_IS_64BIT 'system tar can read our huge size' '
 	test_cmp expect actual
 '
 
+test_expect_success TIME_IS_64BIT 'set up repository with far-future commit' '
+	rm -f .git/index &&
+	echo foo >file &&
+	git add file &&
+	GIT_COMMITTER_DATE="@17179869183 +0000" \
+		git commit -m "tempori parendum"
+'
+
+test_expect_success TIME_IS_64BIT 'generate tar with future mtime' '
+	git archive HEAD >future.tar
+'
+
+test_expect_success TAR_HUGE,TIME_IS_64BIT,TIME_T_IS_64BIT 'system tar can read our future mtime' '
+	echo 2514 >expect &&
+	tar_info future.tar | cut -d" " -f2 >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success TIME_IS_64BIT 'set up repository with far-future commit' '
 	rm -f .git/index &&
 	echo content >file &&
 	git add file &&
-	GIT_COMMITTER_DATE="@68719476737 +0000" \
+	GIT_TEST_COMMIT_GRAPH=0 GIT_COMMITTER_DATE="@68719476737 +0000" \
 		git commit -m "tempori parendum"
 '
 

gitgitgadget

Hi Abhishek,

In short: everything is all right, except for the now duplicated test names in t5000 after this commit.

Nice writeup, however the last sentence would in my opinion read better in the future tense: we don't use generation number v2 yet. For example:

However, with upcoming switch to using corrected committer date as generation number v2, we will have to load committer date to compute generation number value anyway.

Or something like that - notice the minor addition and changes.

The following is slightly unrelated change, but we agreed that it would be better to not separate them; the need for change to the t5000 test is caused by the change described above.

I think it should be s/loads/load/, as in "would load", but I am not a native English speaker.

The description above is for me does not make it entirely clear that we add new test for handling possible 11-octal digit overflow nearly identical to the existing one, and turn off use of commit-graph file for test that checks handling 12-octal digit overflow.

Jakub Narębski

Hello Dr. Narębski,

Thanks for the change, it looks better!

That's correct - since I have used "would not set" in the first half of sentence, the later half should follow suit too.

Revised the last paragraphs to:

The ustar format (the header format used by most modern tar programs) only has room for 11 (or 12, depending on some implementations) octal digits for the size and mtime of each file.

To test the 11-octal digit implementation, we create a future commit with committer date of 2^34 - 1, which overflows 11-octal digits without overflowing 34-bits of the Commit Data chunk.

To test the 12-octal digit implementation, the smallest committer date possible is 2^36, which overflows the Commit Data chunk and thus commit-graph must be disabled for the test.

Changed, thanks for pointing this out.

Thanks
- Abhishek

From: Abhishek Kumar <[email protected]>

In a preparatory step, let's return timestamp_t values from commit_graph_generation(), use timestamp_t for local variables and define GENERATION_NUMBER_INFINITY as (2 ^ 63 - 1) instead.

We rename GENERATION_NUMBER_MAX to GENERATION_NUMBER_V1_MAX to represent the largest topological level we can store in the commit data chunk.

With corrected commit dates implemented, we will have two such *_MAX variables to denote the largest offset and largest topological level that can be stored.

---
 commit-graph.c | 22 +++++++++++-----------
 commit-graph.h |  4 ++--
 commit-reach.c | 36 ++++++++++++++++++------------------
 commit-reach.h |  2 +-
 commit.c       |  4 ++--
 commit.h       |  4 ++--
 revision.c     | 10 +++++-----
 upload-pack.c  |  2 +-
 8 files changed, 42 insertions(+), 42 deletions(-)

index e8362e144e..bfc532de6f 100644
@@ -99,7 +99,7 @@ uint32_t commit_graph_position(const struct commit *c)
 	return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;
 }
 
-uint32_t commit_graph_generation(const struct commit *c)
+timestamp_t commit_graph_generation(const struct commit *c)
 {
 	struct commit_graph_data *data =
 		commit_graph_data_slab_peek(&commit_graph_data_slab, c);

@@ -144,8 +144,8 @@ static int commit_gen_cmp(const void *va, const void *vb)
 	const struct commit *a = *(const struct commit **)va;
 	const struct commit *b = *(const struct commit **)vb;
 
-	uint32_t generation_a = commit_graph_data_at(a)->generation;
-	uint32_t generation_b = commit_graph_data_at(b)->generation;
+	const timestamp_t generation_a = commit_graph_data_at(a)->generation;
+	const timestamp_t generation_b = commit_graph_data_at(b)->generation;
 	/* lower generation commits first */
 	if (generation_a < generation_b)
 		return -1;

@@ -1350,7 +1350,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 					_("Computing commit graph generation numbers"),
 					ctx->commits.nr);
 	for (i = 0; i < ctx->commits.nr; i++) {
-		uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
+		timestamp_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
 
 		display_progress(ctx->progress, i + 1);
 		if (generation != GENERATION_NUMBER_INFINITY &&

@@ -1383,8 +1383,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 				data->generation = max_generation + 1;
 				pop_commit(&list);
 
-				if (data->generation > GENERATION_NUMBER_MAX)
-					data->generation = GENERATION_NUMBER_MAX;
+				if (data->generation > GENERATION_NUMBER_V1_MAX)
+					data->generation = GENERATION_NUMBER_V1_MAX;
 			}
 		}
 	}

@@ -2404,8 +2404,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
 	for (i = 0; i < g->num_commits; i++) {
 		struct commit *graph_commit, *odb_commit;
 		struct commit_list *graph_parents, *odb_parents;
-		uint32_t max_generation = 0;
-		uint32_t generation;
+		timestamp_t max_generation = 0;
+		timestamp_t generation;
 
 		display_progress(progress, i + 1);
 		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);

@@ -2469,11 +2469,11 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
 			continue;
 
 		/*
-		 * If one of our parents has generation GENERATION_NUMBER_MAX, then
-		 * our generation is also GENERATION_NUMBER_MAX. Decrement to avoid
+		 * If one of our parents has generation GENERATION_NUMBER_V1_MAX, then
+		 * our generation is also GENERATION_NUMBER_V1_MAX. Decrement to avoid
 		 * extra logic in the following condition.
 		 */
-		if (max_generation == GENERATION_NUMBER_MAX)
+		if (max_generation == GENERATION_NUMBER_V1_MAX)
 			max_generation--;
 
 		generation = commit_graph_generation(graph_commit);

index f8e92500c6..8be247fa35 100644
@@ -144,12 +144,12 @@ void disable_commit_graph(struct repository *r);
 
 struct commit_graph_data {
 	uint32_t graph_pos;
-	uint32_t generation;
+	timestamp_t generation;
 };
 
 /*
  * Commits should be parsed before accessing generation, graph positions.
  */
-uint32_t commit_graph_generation(const struct commit *);
+timestamp_t commit_graph_generation(const struct commit *);
 uint32_t commit_graph_position(const struct commit *);
 #endif

index 50175b159e..20b48b872b 100644
@@ -32,12 +32,12 @@ static int queue_has_nonstale(struct prio_queue *queue)
 static struct commit_list *paint_down_to_common(struct repository *r,
 						struct commit *one, int n,
 						struct commit **twos,
-						int min_generation)
+						timestamp_t min_generation)
 {
 	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 	struct commit_list *result = NULL;
 	int i;
-	uint32_t last_gen = GENERATION_NUMBER_INFINITY;
+	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
 
 	if (!min_generation)
 		queue.compare = compare_commits_by_commit_date;

@@ -58,10 +58,10 @@ static struct commit_list *paint_down_to_common(struct repository *r,
 		struct commit *commit = prio_queue_get(&queue);
 		struct commit_list *parents;
 		int flags;
-		uint32_t generation = commit_graph_generation(commit);
+		timestamp_t generation = commit_graph_generation(commit);
 
 		if (min_generation && generation > last_gen)
-			BUG("bad generation skip %8x > %8x at %s",
+			BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
 			    generation, last_gen,
 			    oid_to_hex(&commit->object.oid));
 		last_gen = generation;

@@ -177,12 +177,12 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt
 		repo_parse_commit(r, array[i]);
 	for (i = 0; i < cnt; i++) {
 		struct commit_list *common;
-		uint32_t min_generation = commit_graph_generation(array[i]);
+		timestamp_t min_generation = commit_graph_generation(array[i]);
 
 		if (redundant[i])
 			continue;
 		for (j = filled = 0; j < cnt; j++) {
-			uint32_t curr_generation;
+			timestamp_t curr_generation;
 			if (i == j || redundant[j])
 				continue;
 			filled_index[filled] = j;

@@ -321,7 +321,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,
 {
 	struct commit_list *bases;
 	int ret = 0, i;
-	uint32_t generation, max_generation = GENERATION_NUMBER_ZERO;
+	timestamp_t generation, max_generation = GENERATION_NUMBER_INFINITY;
 
 	if (repo_parse_commit(r, commit))
 		return ret;

@@ -470,7 +470,7 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
 static enum contains_result contains_test(struct commit *candidate,
 					  const struct commit_list *want,
 					  struct contains_cache *cache,
-					  uint32_t cutoff)
+					  timestamp_t cutoff)
 {
 	enum contains_result *cached = contains_cache_at(cache, candidate);
 

@@ -506,11 +506,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 {
 	struct contains_stack contains_stack = { 0, 0, NULL };
 	enum contains_result result;
-	uint32_t cutoff = GENERATION_NUMBER_INFINITY;
+	timestamp_t cutoff = GENERATION_NUMBER_INFINITY;
 	const struct commit_list *p;
 
 	for (p = want; p; p = p->next) {
-		uint32_t generation;
+		timestamp_t generation;
 		struct commit *c = p->item;
 		load_commit_graph_info(the_repository, c);
 		generation = commit_graph_generation(c);

@@ -566,8 +566,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	const struct commit *a = *(const struct commit * const *)_a;
 	const struct commit *b = *(const struct commit * const *)_b;
 
-	uint32_t generation_a = commit_graph_generation(a);
-	uint32_t generation_b = commit_graph_generation(b);
+	timestamp_t generation_a = commit_graph_generation(a);
+	timestamp_t generation_b = commit_graph_generation(b);
 
 	if (generation_a < generation_b)
 		return -1;

@@ -580,7 +580,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,
 				 unsigned int assign_flag,
 				 time_t min_commit_date,
-				 uint32_t min_generation)
+				 timestamp_t min_generation)
 {
 	struct commit **list = NULL;
 	int i;

@@ -681,13 +681,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 	time_t min_commit_date = cutoff_by_min_date ? from->item->date : 0;
 	struct commit_list *from_iter = from, *to_iter = to;
 	int result;
-	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
+	timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
 
 	while (from_iter) {
 		add_object_array(&from_iter->item->object, NULL, &from_objs);
 
 		if (!parse_commit(from_iter->item)) {
-			uint32_t generation;
+			timestamp_t generation;
 			if (from_iter->item->date < min_commit_date)
 				min_commit_date = from_iter->item->date;
 

@@ -701,7 +701,7 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 
 	while (to_iter) {
 		if (!parse_commit(to_iter->item)) {
-			uint32_t generation;
+			timestamp_t generation;
 			if (to_iter->item->date < min_commit_date)
 				min_commit_date = to_iter->item->date;
 

@@ -741,13 +741,13 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
 	struct commit_list *found_commits = NULL;
 	struct commit **to_last = to + nr_to;
 	struct commit **from_last = from + nr_from;
-	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
+	timestamp_t min_generation = GENERATION_NUMBER_INFINITY;
 	int num_to_find = 0;
 
 	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
 
 	for (item = to; item < to_last; item++) {
-		uint32_t generation;
+		timestamp_t generation;
 		struct commit *c = *item;
 
 		parse_commit(c);

index b49ad71a31..148b56fea5 100644
@@ -87,7 +87,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,
 				 unsigned int assign_flag,
 				 time_t min_commit_date,
-				 uint32_t min_generation);
+				 timestamp_t min_generation);
 int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 		       int commit_date_cutoff);
 

index f53429c0ac..3b488381d5 100644
@@ -731,8 +731,8 @@ int compare_commits_by_author_date(const void *a_, const void *b_,
 int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
 {
 	const struct commit *a = a_, *b = b_;
-	const uint32_t generation_a = commit_graph_generation(a),
-		       generation_b = commit_graph_generation(b);
+	const timestamp_t generation_a = commit_graph_generation(a),
+			  generation_b = commit_graph_generation(b);
 
 	/* newer commits first */
 	if (generation_a < generation_b)

index 5467786c7b..33c66b2177 100644
@@ -11,8 +11,8 @@
 #include "commit-slab.h"
 
 #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF
-#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF
-#define GENERATION_NUMBER_MAX 0x3FFFFFFF
+#define GENERATION_NUMBER_INFINITY ((1ULL << 63) - 1)
+#define GENERATION_NUMBER_V1_MAX 0x3FFFFFFF
 #define GENERATION_NUMBER_ZERO 0
 
 struct commit_list {

index c97abcdde1..2861f1c45c 100644
@@ -3308,7 +3308,7 @@ define_commit_slab(indegree_slab, int);
 define_commit_slab(author_date_slab, timestamp_t);
 
 struct topo_walk_info {
-	uint32_t min_generation;
+	timestamp_t min_generation;
 	struct prio_queue explore_queue;
 	struct prio_queue indegree_queue;
 	struct prio_queue topo_queue;

@@ -3354,7 +3354,7 @@ static void explore_walk_step(struct rev_info *revs)
 }
 
 static void explore_to_depth(struct rev_info *revs,
-			     uint32_t gen_cutoff)
+			     timestamp_t gen_cutoff)
 {
 	struct topo_walk_info *info = revs->topo_walk_info;
 	struct commit *c;

@@ -3397,7 +3397,7 @@ static void indegree_walk_step(struct rev_info *revs)
 }
 
 static void compute_indegrees_to_depth(struct rev_info *revs,
-				       uint32_t gen_cutoff)
+				       timestamp_t gen_cutoff)
 {
 	struct topo_walk_info *info = revs->topo_walk_info;
 	struct commit *c;

@@ -3455,7 +3455,7 @@ static void init_topo_walk(struct rev_info *revs)
 	info->min_generation = GENERATION_NUMBER_INFINITY;
 	for (list = revs->commits; list; list = list->next) {
 		struct commit *c = list->item;
-		uint32_t generation;
+		timestamp_t generation;
 
 		if (repo_parse_commit_gently(revs->repo, c, 1))
 			continue;

@@ -3516,7 +3516,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
 	for (p = commit->parents; p; p = p->next) {
 		struct commit *parent = p->item;
 		int *pi;
-		uint32_t generation;
+		timestamp_t generation;
 
 		if (parent->object.flags & UNINTERESTING)
 			continue;

index 3b858eb457..fdb82885b6 100644
@@ -497,7 +497,7 @@ static int got_oid(struct upload_pack_data *data,
 
 static int ok_to_give_up(struct upload_pack_data *data)
 {
-	uint32_t min_generation = GENERATION_NUMBER_ZERO;
+	timestamp_t min_generation = GENERATION_NUMBER_ZERO;
 
 	if (!data->have_obj.nr)
 		return 0;

gitgitgadget

Hi Abhishek,

I think it would be easier to understand if it was explicitely said what this preparatory step prepares for, e.g.:

In a preparatory step for introducing corrected commit dates as generation number, let's return timestamp_t values from...

Or even

generation number, let's change the return type of commit_graph_generation() to timestamp_t, and use ...

Otherwise it looks good.

All right, nice explanation.

Note that there are two changes that are not mentioned in the commit message, namely adding 'const'-ness to generation_a/b local variables in commit_gen_cmp() from commit-graph.c, and switching from GENERATION_NUMBER_ZERO to GENERATION_NUMBER_INFINITY as the default (initial) value for 'max_generation' in repo_in_merge_bases_many().

While the former is a simple "while-at-it" change that shouldn't affect correctness, the latter needs an explanation (or fixing if it is wrong).