[PATCH 0/5] Generation Number v2: Fix a tricky split graph bug

[PATCH 0/5] Generation Number v2: Fix a tricky split graph bug

[Derrick Stolee via GitGitGadget]

Here is a bugfix for the recently-landed-in-next generation v2 topic
(ak/corrected-commit-date).

This was occasionally hitting us when computing new commit-graphs on
existing repositories with the new bits. It was very hard to reproduce, and
it turns out to be due to not parsing commits before accessing generation
number data. Doing so in the right place demonstrates the bug of recomputing
the corrected commit date even for commits in lower layers with computed
values.

The fix is split into these steps:

 1. Parse commits more often before accessing their data. (This allows the
    bug to be demonstrated in the test suite.)
 2. Check the full commit-graph chain for generation data chunks.
 3. Don't compute corrected commit dates if the lower layers do not support
    them.
 4. Parse the commit-graph file more often.

Thanks, -Stolee

Derrick Stolee (5):
  commit-graph: use repo_parse_commit
  commit-graph: always parse before commit_graph_data_at()
  commit-graph: validate layers for generation data
  commit-graph: be extra careful about mixed generations
  commit-graph: prepare commit graph

 commit-graph.c          | 87 ++++++++++++++++++++++++++---------------
 commit.h                |  5 ++-
 t/t5318-commit-graph.sh | 21 ++++++++++
 3 files changed, 79 insertions(+), 34 deletions(-)


base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-850%2Fderrickstolee%2Fgen-v2-upgrade-fix-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-850/derrickstolee/gen-v2-upgrade-fix-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/850
-- 
gitgitgadget

[PATCH 1/5] commit-graph: use repo_parse_commit

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The write_commit_graph_context has a repository pointer, so use it.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 10 +++++-----
 commit.h       |  5 +++--
 2 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index f3bde2ad95a..03e5a987968 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1098,7 +1098,7 @@ static int write_graph_chunk_data(struct hashfile *f,
 		uint32_t packedDate[2];
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
-		if (parse_commit_no_graph(*list))
+		if (repo_parse_commit_no_graph(ctx->r, *list))
 			die(_("unable to parse commit %s"),
 				oid_to_hex(&(*list)->object.oid));
 		tree = get_commit_tree_oid(*list);
@@ -1411,11 +1411,11 @@ static void close_reachable(struct write_commit_graph_context *ctx)
 		if (!commit)
 			continue;
 		if (ctx->split) {
-			if ((!parse_commit(commit) &&
+			if ((!repo_parse_commit(ctx->r, commit) &&
 			     commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||
 			    flags == COMMIT_GRAPH_SPLIT_REPLACE)
 				add_missing_parents(ctx, commit);
-		} else if (!parse_commit_no_graph(commit))
+		} else if (!repo_parse_commit_no_graph(ctx->r, commit))
 			add_missing_parents(ctx, commit);
 	}
 	stop_progress(&ctx->progress);
@@ -1710,9 +1710,9 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)
 			continue;
 
 		if (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)
-			parse_commit(ctx->commits.list[ctx->commits.nr]);
+			repo_parse_commit(ctx->r, ctx->commits.list[ctx->commits.nr]);
 		else
-			parse_commit_no_graph(ctx->commits.list[ctx->commits.nr]);
+			repo_parse_commit_no_graph(ctx->r, ctx->commits.list[ctx->commits.nr]);
 
 		num_parents = commit_list_count(ctx->commits.list[ctx->commits.nr]->parents);
 		if (num_parents > 2)
diff --git a/commit.h b/commit.h
index 251d877fcf6..b05ab558ce2 100644
--- a/commit.h
+++ b/commit.h
@@ -89,9 +89,10 @@ static inline int repo_parse_commit(struct repository *r, struct commit *item)
 	return repo_parse_commit_gently(r, item, 0);
 }
 
-static inline int parse_commit_no_graph(struct commit *commit)
+static inline int repo_parse_commit_no_graph(struct repository *r,
+					     struct commit *commit)
 {
-	return repo_parse_commit_internal(the_repository, commit, 0, 0);
+	return repo_parse_commit_internal(r, commit, 0, 0);
 }
 
 #ifndef NO_THE_REPOSITORY_COMPATIBILITY_MACROS
-- 
gitgitgadget

[PATCH 2/5] commit-graph: always parse before commit_graph_data_at()

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

There is a subtle failure happening when computing corrected commit
dates with --split enabled. It requires a base layer needing the
generation_data_overflow chunk. Then, the next layer on top
erroneously thinks it needs an overflow chunk due to a bug leading
to recalculating all reachable generation numbers. The output of
the failure is

  BUG: commit-graph.c:1912: expected to write 8 bytes to
  chunk 47444f56, but wrote 0 instead

These "expected" 8 bytes are due to re-computing the corrected
commit date for the lower layer but the new layer does not need
any overflow.

Add a test to t5318-commit-graph.sh that demonstrates this bug. However,
it does not trigger consistently with the existing code.

The generation number data is stored in a slab and accessed by
commit_graph_data_at(). This data is initialized when parsing a commit,
but is otherwise used assuming it has been populated. The loop in
compute_generation_numbers() did not enforce that all reachable
commits were parsed and had correct values. This could lead to some
problems when writing a commit-graph with corrected commit dates based
on a commit-graph without them.

It has been difficult to identify the issue here becaus it was so hard
to reproduce. It relies on this uninitialized data having a non-zero
value, but also on specifically in a way that overwrites the existing
data.

This patch adds the extra parse to ensure the data is filled before we
compute the generation number of a commit. This triggers the new test
to fail because the generation number overflow count does not match
between this computation and the write for that chunk.

The actual fix will follow as the next few changes.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c          | 16 ++++++++++++----
 t/t5318-commit-graph.sh | 21 +++++++++++++++++++++
 2 files changed, 33 insertions(+), 4 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 03e5a987968..edbb3a0f2cc 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1193,7 +1193,9 @@ static int write_graph_chunk_generation_data(struct hashfile *f,
 
 	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;
+		timestamp_t offset;
+		repo_parse_commit(ctx->r, c);
+		offset = commit_graph_data_at(c)->generation - c->date;
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
 		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
@@ -1444,15 +1446,20 @@ 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 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;
+		struct commit *c = ctx->commits.list[i];
+		uint32_t level;
+		timestamp_t corrected_commit_date;
+
+		repo_parse_commit(ctx->r, c);
+		level = *topo_level_slab_at(ctx->topo_levels, c);
+		corrected_commit_date = commit_graph_data_at(c)->generation;
 
 		display_progress(ctx->progress, i + 1);
 		if (level != GENERATION_NUMBER_ZERO &&
 		    corrected_commit_date != GENERATION_NUMBER_ZERO)
 			continue;
 
-		commit_list_insert(ctx->commits.list[i], &list);
+		commit_list_insert(c, &list);
 		while (list) {
 			struct commit *current = list->item;
 			struct commit_list *parent;
@@ -1461,6 +1468,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 			timestamp_t max_corrected_commit_date = 0;
 
 			for (parent = current->parents; parent; parent = parent->next) {
+				repo_parse_commit(ctx->r, parent->item);
 				level = *topo_level_slab_at(ctx->topo_levels, parent->item);
 				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
 
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index fa27df579a5..2cf29f425a0 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -446,6 +446,27 @@ test_expect_success 'warn on improper hash version' '
 	)
 '
 
+test_expect_failure 'lower layers have overflow chunk' '
+	cd "$TRASH_DIRECTORY/full" &&
+	UNIX_EPOCH_ZERO="@0 +0000" &&
+	FUTURE_DATE="@2147483646 +0000" &&
+	rm -f .git/objects/info/commit-graph &&
+	test_commit --date "$FUTURE_DATE" future-1 &&
+	test_commit --date "$UNIX_EPOCH_ZERO" old-1 &&
+	git commit-graph write --reachable &&
+	test_commit --date "$FUTURE_DATE" future-2 &&
+	test_commit --date "$UNIX_EPOCH_ZERO" old-2 &&
+	git commit-graph write --reachable --split=no-merge &&
+	test_commit extra &&
+	git commit-graph write --reachable --split=no-merge &&
+	git commit-graph write --reachable &&
+	graph_read_expect 16 "generation_data generation_data_overflow extra_edges" &&
+	mv .git/objects/info/commit-graph commit-graph-upgraded &&
+	git commit-graph write --reachable &&
+	graph_read_expect 16 "generation_data generation_data_overflow extra_edges" &&
+	test_cmp .git/objects/info/commit-graph commit-graph-upgraded
+'
+
 # the verify tests below expect the commit-graph to contain
 # exactly the commits reachable from the commits/8 branch.
 # If the file changes the set of commits in the list, then the
-- 
gitgitgadget

[PATCH 3/5] commit-graph: validate layers for generation data

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

We need to be extra careful that we don't use corrected
commit dates from any layer of a commit-graph chain if there is a
single commit-graph file that is missing the generation_data chunk.
Update validate_mixed_generation_chain() to correctly update each
layer to ignore the generation_data chunk in this case. It now also
returns 1 if all layers have a generation_data chunk. This return
value will be used in the next change.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index edbb3a0f2cc..13992137dd0 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -614,19 +614,26 @@ static struct commit_graph *load_commit_graph_chain(struct repository *r,
 	return graph_chain;
 }
 
-static void validate_mixed_generation_chain(struct commit_graph *g)
+/*
+ * returns 1 if and only if all graphs in the chain have
+ * corrected commit dates stored in the generation_data chunk.
+ */
+static int validate_mixed_generation_chain(struct commit_graph *g)
 {
-	int read_generation_data;
+	int read_generation_data = 1;
+	struct commit_graph *p = g;
 
-	if (!g)
-		return;
-
-	read_generation_data = !!g->chunk_generation_data;
+	while (read_generation_data && p) {
+		read_generation_data = p->read_generation_data;
+		p = p->base_graph;
+	}
 
 	while (g) {
 		g->read_generation_data = read_generation_data;
 		g = g->base_graph;
 	}
+
+	return read_generation_data;
 }
 
 struct commit_graph *read_commit_graph_one(struct repository *r,
-- 
gitgitgadget

[PATCH 4/5] commit-graph: be extra careful about mixed generations

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

When upgrading to a commit-graph with corrected commit dates from
one without, there are a few things that need to be considered.

When computing generation numbers for the new commit-graph file that
expects to add the generation_data chunk with corrected commit
dates, we need to ensure that the 'generation' member of the
commit_graph_data struct is set to zero for these commits.

Unfortunately, the fallback to use topological level for generation
number when corrected commit dates are not available are causing us
harm here: parsing commits notices that read_generation_data is
false and populates 'generation' with the topological level.

The solution is to iterate through the commits, parse the commits
to populate initial values, then reset the generation values to
zero to trigger recalculation. This loop only occurs when the
existing commit-graph data has no corrected commit dates.

While this improves our situation somewhat, we have not completely
solved the issue for correctly computing generation numbers for mixes
layers. That follows in the next change.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 32 +++++++++++++++++++++++---------
 1 file changed, 23 insertions(+), 9 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 13992137dd0..08148dd17f1 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1033,7 +1033,8 @@ struct write_commit_graph_context {
 		 split:1,
 		 changed_paths:1,
 		 order_by_pack:1,
-		 write_generation_data:1;
+		 write_generation_data:1,
+		 trust_generation_numbers:1;
 
 	struct topo_level_slab *topo_levels;
 	const struct commit_graph_opts *opts;
@@ -1452,6 +1453,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 		ctx->progress = start_delayed_progress(
 					_("Computing commit graph generation numbers"),
 					ctx->commits.nr);
+
+	if (ctx->write_generation_data && !ctx->trust_generation_numbers) {
+		for (i = 0; i < ctx->commits.nr; i++) {
+			struct commit *c = ctx->commits.list[i];
+			repo_parse_commit(ctx->r, c);
+			commit_graph_data_at(c)->generation = GENERATION_NUMBER_ZERO;
+		}
+	}
+
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];
 		uint32_t level;
@@ -1480,7 +1490,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
 
 				if (level == GENERATION_NUMBER_ZERO ||
-				    corrected_commit_date == GENERATION_NUMBER_ZERO) {
+				    (ctx->write_generation_data &&
+				     corrected_commit_date == GENERATION_NUMBER_ZERO)) {
 					all_parents_computed = 0;
 					commit_list_insert(parent->item, &list);
 					break;
@@ -1500,12 +1511,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 					max_level = GENERATION_NUMBER_V1_MAX - 1;
 				*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
 
-				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++;
+				if (ctx->write_generation_data) {
+					timestamp_t cur_g;
+					if (current->date && current->date > max_corrected_commit_date)
+						max_corrected_commit_date = current->date - 1;
+					cur_g = commit_graph_data_at(current)->generation
+					      = max_corrected_commit_date + 1;
+					if (cur_g - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
+						ctx->num_generation_data_overflows++;
+				}
 			}
 		}
 	}
@@ -2396,7 +2410,7 @@ int write_commit_graph(struct object_directory *odb,
 	} else
 		ctx->num_commit_graphs_after = 1;
 
-	validate_mixed_generation_chain(ctx->r->objects->commit_graph);
+	ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
 
 	compute_generation_numbers(ctx);
 
-- 
gitgitgadget

[PATCH 5/5] commit-graph: prepare commit graph

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

Before checking if the repository has a commit-graph loaded, be sure
to run prepare_commit_graph(). This is necessary because without this
instance we would not initialize the topo_levels slab for each of the
struct commit_graphs in the chain before we start to parse the
commits. This leads to possibly recomputing the topological levels for
commits in lower layers even when we are adding a small number of
commits on top.

By properly initializing the topo_slab, we fix the previously broken
case of a split commit graph where a base layer has the
generation_data_overflow chunk.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c          | 10 ++--------
 t/t5318-commit-graph.sh |  2 +-
 2 files changed, 3 insertions(+), 9 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 08148dd17f1..858fa5594e3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -2309,6 +2309,7 @@ int write_commit_graph(struct object_directory *odb,
 	init_topo_level_slab(&topo_levels);
 	ctx->topo_levels = &topo_levels;
 
+	prepare_commit_graph(ctx->r);
 	if (ctx->r->objects->commit_graph) {
 		struct commit_graph *g = ctx->r->objects->commit_graph;
 
@@ -2322,7 +2323,6 @@ int write_commit_graph(struct object_directory *odb,
 		ctx->changed_paths = 1;
 	if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
 		struct commit_graph *g;
-		prepare_commit_graph_one(ctx->r, ctx->odb);
 
 		g = ctx->r->objects->commit_graph;
 
@@ -2334,10 +2334,7 @@ int write_commit_graph(struct object_directory *odb,
 	}
 
 	if (ctx->split) {
-		struct commit_graph *g;
-		prepare_commit_graph(ctx->r);
-
-		g = ctx->r->objects->commit_graph;
+		struct commit_graph *g = ctx->r->objects->commit_graph;
 
 		while (g) {
 			ctx->num_commit_graphs_before++;
@@ -2361,9 +2358,6 @@ int write_commit_graph(struct object_directory *odb,
 
 	ctx->approx_nr_objects = approximate_object_count();
 
-	if (ctx->append)
-		prepare_commit_graph_one(ctx->r, ctx->odb);
-
 	if (ctx->append && ctx->r->objects->commit_graph) {
 		struct commit_graph *g = ctx->r->objects->commit_graph;
 		for (i = 0; i < g->num_commits; i++) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 2cf29f425a0..5b15f1aa0f6 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -446,7 +446,7 @@ test_expect_success 'warn on improper hash version' '
 	)
 '
 
-test_expect_failure 'lower layers have overflow chunk' '
+test_expect_success 'lower layers have overflow chunk' '
 	cd "$TRASH_DIRECTORY/full" &&
 	UNIX_EPOCH_ZERO="@0 +0000" &&
 	FUTURE_DATE="@2147483646 +0000" &&
-- 
gitgitgadget

Re: [PATCH 1/5] commit-graph: use repo_parse_commit

[Taylor Blau]

On Mon, Feb 01, 2021 at 05:15:03PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <dstolee@microsoft.com>
>
> The write_commit_graph_context has a repository pointer, so use it.
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>

Everything here looks good to me, but...

> ---
>  commit-graph.c | 10 +++++-----
>  commit.h       |  5 +++--
>  2 files changed, 8 insertions(+), 7 deletions(-)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index f3bde2ad95a..03e5a987968 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -1098,7 +1098,7 @@ static int write_graph_chunk_data(struct hashfile *f,
>  		uint32_t packedDate[2];
>  		display_progress(ctx->progress, ++ctx->progress_cnt);
>
> -		if (parse_commit_no_graph(*list))
> +		if (repo_parse_commit_no_graph(ctx->r, *list))
>  			die(_("unable to parse commit %s"),
>  				oid_to_hex(&(*list)->object.oid));
>  		tree = get_commit_tree_oid(*list);
> @@ -1411,11 +1411,11 @@ static void close_reachable(struct write_commit_graph_context *ctx)
>  		if (!commit)
>  			continue;
>  		if (ctx->split) {
> -			if ((!parse_commit(commit) &&
> +			if ((!repo_parse_commit(ctx->r, commit) &&

I know that this has nothing to do with your patch, but it really would
be nice to unify all of these parse_commit() vs parse_commit_no_graph()
calls.

As I recall this dates back to 43d3561805 (commit-graph write: don't die
if the existing graph is corrupt, 2019-03-25), and there was some
discussion on the list at the time about revisiting this if we ever were
able to write incremental commit graphs:

  https://lore.kernel.org/git/20190221223753.20070-8-avarab@gmail.com/

Now may be a good time to revisit that, although I don't want to detract
from another fix (that we really do need to land before v2.31.0).

Thanks,
Taylor

Re: [PATCH 3/5] commit-graph: validate layers for generation data

[Taylor Blau]

On Mon, Feb 01, 2021 at 05:15:05PM +0000, Derrick Stolee via GitGitGadget wrote:
> diff --git a/commit-graph.c b/commit-graph.c
> index edbb3a0f2cc..13992137dd0 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -614,19 +614,26 @@ static struct commit_graph *load_commit_graph_chain(struct repository *r,
>  	return graph_chain;
>  }
>
> -static void validate_mixed_generation_chain(struct commit_graph *g)
> +/*
> + * returns 1 if and only if all graphs in the chain have
> + * corrected commit dates stored in the generation_data chunk.
> + */
> +static int validate_mixed_generation_chain(struct commit_graph *g)

Thanks for the comment. It does make me wonder if the function name
needs updating, though. I'm having some trouble coming up with a better
alternative, though, so maybe it's fine...

>  {
> -	int read_generation_data;
> +	int read_generation_data = 1;

OK, we might not ever enter the while loops below, so this needs
initializing.

> +	struct commit_graph *p = g;
>
> -	if (!g)
> -		return;
> -
> -	read_generation_data = !!g->chunk_generation_data;
> +	while (read_generation_data && p) {
> +		read_generation_data = p->read_generation_data;
> +		p = p->base_graph;
> +	}

This could probably be guarded with an 'if !read_generation_data', since
if the previous while loop always read '1' from
'p->read_generation_data', then nothing needs updating, no?

(If you do make this change, please don't add '!read_generation_data' to
the while expression, since it isn't a property of the loop.)

>  	while (g) {
>  		g->read_generation_data = read_generation_data;
>  		g = g->base_graph;
>  	}
> +
> +	return read_generation_data;
>  }
>
>  struct commit_graph *read_commit_graph_one(struct repository *r,
> --
> gitgitgadget
>

Thanks,
Taylor

Re: [PATCH 4/5] commit-graph: be extra careful about mixed generations

[Taylor Blau]

On Mon, Feb 01, 2021 at 05:15:06PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <dstolee@microsoft.com>
>
> When upgrading to a commit-graph with corrected commit dates from
> one without, there are a few things that need to be considered.
>
> When computing generation numbers for the new commit-graph file that
> expects to add the generation_data chunk with corrected commit
> dates, we need to ensure that the 'generation' member of the
> commit_graph_data struct is set to zero for these commits.
>
> Unfortunately, the fallback to use topological level for generation
> number when corrected commit dates are not available are causing us
> harm here: parsing commits notices that read_generation_data is
> false and populates 'generation' with the topological level.
>
> The solution is to iterate through the commits, parse the commits
> to populate initial values, then reset the generation values to
> zero to trigger recalculation. This loop only occurs when the
> existing commit-graph data has no corrected commit dates.
>
> While this improves our situation somewhat, we have not completely
> solved the issue for correctly computing generation numbers for mixes
> layers. That follows in the next change.
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  commit-graph.c | 32 +++++++++++++++++++++++---------
>  1 file changed, 23 insertions(+), 9 deletions(-)
>
> diff --git a/commit-graph.c b/commit-graph.c
> index 13992137dd0..08148dd17f1 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -1033,7 +1033,8 @@ struct write_commit_graph_context {
>  		 split:1,
>  		 changed_paths:1,
>  		 order_by_pack:1,
> -		 write_generation_data:1;
> +		 write_generation_data:1,
> +		 trust_generation_numbers:1;
>
>  	struct topo_level_slab *topo_levels;
>  	const struct commit_graph_opts *opts;
> @@ -1452,6 +1453,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>  		ctx->progress = start_delayed_progress(
>  					_("Computing commit graph generation numbers"),
>  					ctx->commits.nr);
> +
> +	if (ctx->write_generation_data && !ctx->trust_generation_numbers) {
> +		for (i = 0; i < ctx->commits.nr; i++) {
> +			struct commit *c = ctx->commits.list[i];
> +			repo_parse_commit(ctx->r, c);
> +			commit_graph_data_at(c)->generation = GENERATION_NUMBER_ZERO;
> +		}
> +	}
> +

This took me a while to figure out since I spent quite a lot of time
thinking that you were setting the topological level to zero, _not_ the
corrected committer date.

Now that I understand which is which, I agree that this is the right way
to go forward.

That said, I do find it unnecessarily complex that we compute both the
generation number and the topological level in the same loops in
compute_generation_numbers()...

>  	for (i = 0; i < ctx->commits.nr; i++) {
>  		struct commit *c = ctx->commits.list[i];
>  		uint32_t level;
> @@ -1480,7 +1490,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>  				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
>
>  				if (level == GENERATION_NUMBER_ZERO ||
> -				    corrected_commit_date == GENERATION_NUMBER_ZERO) {
> +				    (ctx->write_generation_data &&
> +				     corrected_commit_date == GENERATION_NUMBER_ZERO)) {

...for exactly reasons like this. It does make sense that they could be
computed together since their computation is indeed quite similar. But
in practice I think you end up spending a lot of time reasoning around
complex conditionals like these.

So, I feel a little bit like we should spend some effort to split these
up. I'm OK with a little bit of code duplication (though if we can
factor out some common routine, that would also be nice). But I think
there's a tradeoff between DRY-ness and understandability, and that we
might be on the wrong side of it here.

>  					all_parents_computed = 0;
>  					commit_list_insert(parent->item, &list);
>  					break;
> @@ -1500,12 +1511,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>  					max_level = GENERATION_NUMBER_V1_MAX - 1;
>  				*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
>
> -				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++;
> +				if (ctx->write_generation_data) {
> +					timestamp_t cur_g;
> +					if (current->date && current->date > max_corrected_commit_date)
> +						max_corrected_commit_date = current->date - 1;
> +					cur_g = commit_graph_data_at(current)->generation
> +					      = max_corrected_commit_date + 1;
> +					if (cur_g - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
> +						ctx->num_generation_data_overflows++;
> +				}

Looks like two things happened here:

  - A new local variable was introduced to store the value of
    'commit_graph_data_at(current)->generation' (now called 'cur_g'),
    and

  - All of this was guarded by a conditional on
    'ctx->write_generation_data'.

The first one is a readability improvement, and the second is the
substantive one, no?

>  			}
>  		}
>  	}
> @@ -2396,7 +2410,7 @@ int write_commit_graph(struct object_directory *odb,
>  	} else
>  		ctx->num_commit_graphs_after = 1;
>
> -	validate_mixed_generation_chain(ctx->r->objects->commit_graph);
> +	ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
>
>  	compute_generation_numbers(ctx);

Makes sense.

Thanks,
Taylor

Re: [PATCH 3/5] commit-graph: validate layers for generation data

[Derrick Stolee]

On 2/1/2021 12:39 PM, Taylor Blau wrote:
> On Mon, Feb 01, 2021 at 05:15:05PM +0000, Derrick Stolee via GitGitGadget wrote:
>> +	struct commit_graph *p = g;
>>
>> -	if (!g)
>> -		return;
>> -
>> -	read_generation_data = !!g->chunk_generation_data;
>> +	while (read_generation_data && p) {
>> +		read_generation_data = p->read_generation_data;
>> +		p = p->base_graph;
>> +	}
> 
> This could probably be guarded with an 'if !read_generation_data', since
> if the previous while loop always read '1' from
> 'p->read_generation_data', then nothing needs updating, no?
> 
> (If you do make this change, please don't add '!read_generation_data' to
> the while expression, since it isn't a property of the loop.)

True, we could do that. It's enough to add

	if (read_generation_data)
		return 1;

>>  	while (g) {
>>  		g->read_generation_data = read_generation_data;
>>  		g = g->base_graph;
>>  	}
>> +
>> +	return read_generation_data;

then this becomes

	return 0;

Thanks,
-Stolee

Re: [PATCH 4/5] commit-graph: be extra careful about mixed generations

[Derrick Stolee]

On 2/1/2021 1:04 PM, Taylor Blau wrote:
> On Mon, Feb 01, 2021 at 05:15:06PM +0000, Derrick Stolee via GitGitGadget wrote:
...
>>  	struct topo_level_slab *topo_levels;
>>  	const struct commit_graph_opts *opts;
>> @@ -1452,6 +1453,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>>  		ctx->progress = start_delayed_progress(
>>  					_("Computing commit graph generation numbers"),
>>  					ctx->commits.nr);
>> +
>> +	if (ctx->write_generation_data && !ctx->trust_generation_numbers) {
>> +		for (i = 0; i < ctx->commits.nr; i++) {
>> +			struct commit *c = ctx->commits.list[i];
>> +			repo_parse_commit(ctx->r, c);
>> +			commit_graph_data_at(c)->generation = GENERATION_NUMBER_ZERO;
>> +		}
>> +	}
>> +
> 
> This took me a while to figure out since I spent quite a lot of time
> thinking that you were setting the topological level to zero, _not_ the
> corrected committer date.
> 
> Now that I understand which is which, I agree that this is the right way
> to go forward.
> 
> That said, I do find it unnecessarily complex that we compute both the
> generation number and the topological level in the same loops in
> compute_generation_numbers()...
> 
>>  	for (i = 0; i < ctx->commits.nr; i++) {
>>  		struct commit *c = ctx->commits.list[i];
>>  		uint32_t level;
>> @@ -1480,7 +1490,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>>  				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
>>
>>  				if (level == GENERATION_NUMBER_ZERO ||
>> -				    corrected_commit_date == GENERATION_NUMBER_ZERO) {
>> +				    (ctx->write_generation_data &&
>> +				     corrected_commit_date == GENERATION_NUMBER_ZERO)) {
> 
> ...for exactly reasons like this. It does make sense that they could be
> computed together since their computation is indeed quite similar. But
> in practice I think you end up spending a lot of time reasoning around
> complex conditionals like these.
> 
> So, I feel a little bit like we should spend some effort to split these
> up. I'm OK with a little bit of code duplication (though if we can
> factor out some common routine, that would also be nice). But I think
> there's a tradeoff between DRY-ness and understandability, and that we
> might be on the wrong side of it here.

You're probably right that it is valuable to split the computations.
It would allow us to skip all of the "if (ctx->write_generation_data)"
checks in this implementation and rely on the callers to make that
choice.

>>  					all_parents_computed = 0;
>>  					commit_list_insert(parent->item, &list);
>>  					break;
>> @@ -1500,12 +1511,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>>  					max_level = GENERATION_NUMBER_V1_MAX - 1;
>>  				*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
>>
>> -				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++;
>> +				if (ctx->write_generation_data) {
>> +					timestamp_t cur_g;
>> +					if (current->date && current->date > max_corrected_commit_date)
>> +						max_corrected_commit_date = current->date - 1;
>> +					cur_g = commit_graph_data_at(current)->generation
>> +					      = max_corrected_commit_date + 1;
>> +					if (cur_g - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
>> +						ctx->num_generation_data_overflows++;
>> +				}
> 
> Looks like two things happened here:
> 
>   - A new local variable was introduced to store the value of
>     'commit_graph_data_at(current)->generation' (now called 'cur_g'),
>     and
> 
>   - All of this was guarded by a conditional on
>     'ctx->write_generation_data'.
> 
> The first one is a readability improvement, and the second is the
> substantive one, no?

Yes. Adding these checks and tabs made things super-wide, so cur_g
exists only for readability. If we split the computation, then this
is no longer required.

Thanks,
-Stolee

Re: [PATCH 5/5] commit-graph: prepare commit graph

[Taylor Blau]

On Mon, Feb 01, 2021 at 05:15:07PM +0000, Derrick Stolee via GitGitGadget wrote:
> From: Derrick Stolee <dstolee@microsoft.com>
>
> Before checking if the repository has a commit-graph loaded, be sure
> to run prepare_commit_graph(). This is necessary because without this
> instance we would not initialize the topo_levels slab for each of the
> struct commit_graphs in the chain before we start to parse the
> commits. This leads to possibly recomputing the topological levels for
> commits in lower layers even when we are adding a small number of
> commits on top.

I think that the situation arises as follows:

  - Prior to this patch, we didn't always prepare the commit-graph, so
    the topo_levels slab wasn't initialized either.

  - Then we try and compute the topo levels for new commits (which are
    likely to be decendants of older ones that are in commit-graphs and
    have their topo-levels already computed).

  - But in the course of computing topo-levels for the new commits, we
    have to recur on their ancestors, which *look* like they have
    uncomputed topo levels.

That all makes sense, but it may be worth cutting and pasting what I
wrote into your patch to make it clearer.

> By properly initializing the topo_slab, we fix the previously broken
> case of a split commit graph where a base layer has the
> generation_data_overflow chunk.

Makes sense.

> -test_expect_failure 'lower layers have overflow chunk' '
> +test_expect_success 'lower layers have overflow chunk' '
>  	cd "$TRASH_DIRECTORY/full" &&
>  	UNIX_EPOCH_ZERO="@0 +0000" &&
>  	FUTURE_DATE="@2147483646 +0000" &&

Terrific :-).

Thanks,
Taylor

Re: [PATCH 2/5] commit-graph: always parse before commit_graph_data_at()

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> It has been difficult to identify the issue here becaus it was so hard

"because" (will fix-up locally).

> to reproduce. It relies on this uninitialized data having a non-zero
> value, but also on specifically in a way that overwrites the existing
> data.

Re: [PATCH 4/5] commit-graph: be extra careful about mixed generations

[Junio C Hamano]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Derrick Stolee <dstolee@microsoft.com>
>
> When upgrading to a commit-graph with corrected commit dates from
> one without, there are a few things that need to be considered.
>
> When computing generation numbers for the new commit-graph file that
> expects to add the generation_data chunk with corrected commit
> dates, we need to ensure that the 'generation' member of the
> commit_graph_data struct is set to zero for these commits.
>
> Unfortunately, the fallback to use topological level for generation
> number when corrected commit dates are not available are causing us
> harm here: parsing commits notices that read_generation_data is
> false and populates 'generation' with the topological level.
>
> The solution is to iterate through the commits, parse the commits
> to populate initial values, then reset the generation values to
> zero to trigger recalculation. This loop only occurs when the
> existing commit-graph data has no corrected commit dates.
>
> While this improves our situation somewhat, we have not completely
> solved the issue for correctly computing generation numbers for mixes

"mixed"? (will not touch locally).

> layers. That follows in the next change.
>
> Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
> ---
>  commit-graph.c | 32 +++++++++++++++++++++++---------
>  1 file changed, 23 insertions(+), 9 deletions(-)

The hunks that mention trust_generation_numbers match what the
commit log message says what the patch does, but other two hunks
that make sure that some code that used to run regardless of the
value of "ctx->write_generation_data" are now run only when the
member is nonzero smells like an unrelated change.

Thanks.

[PATCH v2 0/6] Generation Number v2: Fix a tricky split graph bug

[Derrick Stolee via GitGitGadget]

Here is a bugfix for the recently-landed-in-next generation v2 topic
(ak/corrected-commit-date).

This was occasionally hitting us when computing new commit-graphs on
existing repositories with the new bits. It was very hard to reproduce, and
it turns out to be due to not parsing commits before accessing generation
number data. Doing so in the right place demonstrates the bug of recomputing
the corrected commit date even for commits in lower layers with computed
values.

The fix is split into these steps:

 1. Parse commits more often before accessing their data. (This allows the
    bug to be demonstrated in the test suite.)
 2. Check the full commit-graph chain for generation data chunks.
 3. Don't compute corrected commit dates if the lower layers do not support
    them.
 4. Parse the commit-graph file more often.

Thanks, -Stolee


Updates in v2
=============

 * Fixed some typos or other clarifications in commit messages.

 * The loop assigning read_generation_data is skipped if they already all
   agree with value 1.

 * I split compute_generation_numbers into two methods. This essentially
   splits the previous patch 4 into patches 4 & 5 here. The new patch 4 just
   splits the logic as-is, then the new patch 5 does the re-initialization
   of generation values when in the upgrade scenario.

Derrick Stolee (6):
  commit-graph: use repo_parse_commit
  commit-graph: always parse before commit_graph_data_at()
  commit-graph: validate layers for generation data
  commit-graph: compute generations separately
  commit-graph: be extra careful about mixed generations
  commit-graph: prepare commit graph

 commit-graph.c          | 138 +++++++++++++++++++++++++++++-----------
 commit.h                |   5 +-
 t/t5318-commit-graph.sh |  21 ++++++
 3 files changed, 125 insertions(+), 39 deletions(-)


base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-850%2Fderrickstolee%2Fgen-v2-upgrade-fix-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-850/derrickstolee/gen-v2-upgrade-fix-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/850

Range-diff vs v1:

 1:  9c605c99f66 = 1:  9c605c99f66 commit-graph: use repo_parse_commit
 2:  82afa811dff ! 2:  454b183b9ba commit-graph: always parse before commit_graph_data_at()
     @@ Commit message
          problems when writing a commit-graph with corrected commit dates based
          on a commit-graph without them.
      
     -    It has been difficult to identify the issue here becaus it was so hard
     +    It has been difficult to identify the issue here because it was so hard
          to reproduce. It relies on this uninitialized data having a non-zero
          value, but also on specifically in a way that overwrites the existing
          data.
 3:  d554fa30660 ! 3:  3d223fa2156 commit-graph: validate layers for generation data
     @@ commit-graph.c: static struct commit_graph *load_commit_graph_chain(struct repos
       
      -	if (!g)
      -		return;
     --
     --	read_generation_data = !!g->chunk_generation_data;
      +	while (read_generation_data && p) {
      +		read_generation_data = p->read_generation_data;
      +		p = p->base_graph;
      +	}
       
     +-	read_generation_data = !!g->chunk_generation_data;
     ++	if (read_generation_data)
     ++		return 1;
     + 
       	while (g) {
     - 		g->read_generation_data = read_generation_data;
     +-		g->read_generation_data = read_generation_data;
     ++		g->read_generation_data = 0;
       		g = g->base_graph;
       	}
      +
     -+	return read_generation_data;
     ++	return 0;
       }
       
       struct commit_graph *read_commit_graph_one(struct repository *r,
 -:  ----------- > 4:  05248ff222f commit-graph: compute generations separately
 4:  b267a9653a7 ! 5:  9bccee8fb63 commit-graph: be extra careful about mixed generations
     @@ Commit message
          existing commit-graph data has no corrected commit dates.
      
          While this improves our situation somewhat, we have not completely
     -    solved the issue for correctly computing generation numbers for mixes
     +    solved the issue for correctly computing generation numbers for mixed
          layers. That follows in the next change.
      
          Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
     @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
       					_("Computing commit graph generation numbers"),
       					ctx->commits.nr);
      +
     -+	if (ctx->write_generation_data && !ctx->trust_generation_numbers) {
     ++	if (!ctx->trust_generation_numbers) {
      +		for (i = 0; i < ctx->commits.nr; i++) {
      +			struct commit *c = ctx->commits.list[i];
      +			repo_parse_commit(ctx->r, c);
     @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
      +
       	for (i = 0; i < ctx->commits.nr; i++) {
       		struct commit *c = ctx->commits.list[i];
     - 		uint32_t level;
     -@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
     - 				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
     - 
     - 				if (level == GENERATION_NUMBER_ZERO ||
     --				    corrected_commit_date == GENERATION_NUMBER_ZERO) {
     -+				    (ctx->write_generation_data &&
     -+				     corrected_commit_date == GENERATION_NUMBER_ZERO)) {
     - 					all_parents_computed = 0;
     - 					commit_list_insert(parent->item, &list);
     - 					break;
     -@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
     - 					max_level = GENERATION_NUMBER_V1_MAX - 1;
     - 				*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
     - 
     --				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++;
     -+				if (ctx->write_generation_data) {
     -+					timestamp_t cur_g;
     -+					if (current->date && current->date > max_corrected_commit_date)
     -+						max_corrected_commit_date = current->date - 1;
     -+					cur_g = commit_graph_data_at(current)->generation
     -+					      = max_corrected_commit_date + 1;
     -+					if (cur_g - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
     -+						ctx->num_generation_data_overflows++;
     -+				}
     - 			}
     - 		}
     - 	}
     + 		timestamp_t corrected_commit_date;
      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
       	} else
       		ctx->num_commit_graphs_after = 1;
     @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
      -	validate_mixed_generation_chain(ctx->r->objects->commit_graph);
      +	ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
       
     - 	compute_generation_numbers(ctx);
     - 
     + 	compute_topological_levels(ctx);
     + 	if (ctx->write_generation_data)
 5:  dddeec30ebf ! 6:  38086c85b52 commit-graph: prepare commit graph
     @@ Commit message
          commit-graph: prepare commit graph
      
          Before checking if the repository has a commit-graph loaded, be sure
     -    to run prepare_commit_graph(). This is necessary because without this
     -    instance we would not initialize the topo_levels slab for each of the
     -    struct commit_graphs in the chain before we start to parse the
     -    commits. This leads to possibly recomputing the topological levels for
     -    commits in lower layers even when we are adding a small number of
     -    commits on top.
     +    to run prepare_commit_graph(). This is necessary because otherwise
     +    the topo_levels slab is not initialized. As we compute topo_levels for
     +    the new commits, we iterate further into the lower layers since the
     +    first visit to each commit looks as though the topo_level is not
     +    populated.
      
          By properly initializing the topo_slab, we fix the previously broken
          case of a split commit graph where a base layer has the

-- 
gitgitgadget

[PATCH v2 1/6] commit-graph: use repo_parse_commit

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The write_commit_graph_context has a repository pointer, so use it.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 10 +++++-----
 commit.h       |  5 +++--
 2 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index f3bde2ad95a..03e5a987968 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1098,7 +1098,7 @@ static int write_graph_chunk_data(struct hashfile *f,
 		uint32_t packedDate[2];
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
-		if (parse_commit_no_graph(*list))
+		if (repo_parse_commit_no_graph(ctx->r, *list))
 			die(_("unable to parse commit %s"),
 				oid_to_hex(&(*list)->object.oid));
 		tree = get_commit_tree_oid(*list);
@@ -1411,11 +1411,11 @@ static void close_reachable(struct write_commit_graph_context *ctx)
 		if (!commit)
 			continue;
 		if (ctx->split) {
-			if ((!parse_commit(commit) &&
+			if ((!repo_parse_commit(ctx->r, commit) &&
 			     commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||
 			    flags == COMMIT_GRAPH_SPLIT_REPLACE)
 				add_missing_parents(ctx, commit);
-		} else if (!parse_commit_no_graph(commit))
+		} else if (!repo_parse_commit_no_graph(ctx->r, commit))
 			add_missing_parents(ctx, commit);
 	}
 	stop_progress(&ctx->progress);
@@ -1710,9 +1710,9 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)
 			continue;
 
 		if (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)
-			parse_commit(ctx->commits.list[ctx->commits.nr]);
+			repo_parse_commit(ctx->r, ctx->commits.list[ctx->commits.nr]);
 		else
-			parse_commit_no_graph(ctx->commits.list[ctx->commits.nr]);
+			repo_parse_commit_no_graph(ctx->r, ctx->commits.list[ctx->commits.nr]);
 
 		num_parents = commit_list_count(ctx->commits.list[ctx->commits.nr]->parents);
 		if (num_parents > 2)
diff --git a/commit.h b/commit.h
index 251d877fcf6..b05ab558ce2 100644
--- a/commit.h
+++ b/commit.h
@@ -89,9 +89,10 @@ static inline int repo_parse_commit(struct repository *r, struct commit *item)
 	return repo_parse_commit_gently(r, item, 0);
 }
 
-static inline int parse_commit_no_graph(struct commit *commit)
+static inline int repo_parse_commit_no_graph(struct repository *r,
+					     struct commit *commit)
 {
-	return repo_parse_commit_internal(the_repository, commit, 0, 0);
+	return repo_parse_commit_internal(r, commit, 0, 0);
 }
 
 #ifndef NO_THE_REPOSITORY_COMPATIBILITY_MACROS
-- 
gitgitgadget

[PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

There is a subtle failure happening when computing corrected commit
dates with --split enabled. It requires a base layer needing the
generation_data_overflow chunk. Then, the next layer on top
erroneously thinks it needs an overflow chunk due to a bug leading
to recalculating all reachable generation numbers. The output of
the failure is

  BUG: commit-graph.c:1912: expected to write 8 bytes to
  chunk 47444f56, but wrote 0 instead

These "expected" 8 bytes are due to re-computing the corrected
commit date for the lower layer but the new layer does not need
any overflow.

Add a test to t5318-commit-graph.sh that demonstrates this bug. However,
it does not trigger consistently with the existing code.

The generation number data is stored in a slab and accessed by
commit_graph_data_at(). This data is initialized when parsing a commit,
but is otherwise used assuming it has been populated. The loop in
compute_generation_numbers() did not enforce that all reachable
commits were parsed and had correct values. This could lead to some
problems when writing a commit-graph with corrected commit dates based
on a commit-graph without them.

It has been difficult to identify the issue here because it was so hard
to reproduce. It relies on this uninitialized data having a non-zero
value, but also on specifically in a way that overwrites the existing
data.

This patch adds the extra parse to ensure the data is filled before we
compute the generation number of a commit. This triggers the new test
to fail because the generation number overflow count does not match
between this computation and the write for that chunk.

The actual fix will follow as the next few changes.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c          | 16 ++++++++++++----
 t/t5318-commit-graph.sh | 21 +++++++++++++++++++++
 2 files changed, 33 insertions(+), 4 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 03e5a987968..edbb3a0f2cc 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1193,7 +1193,9 @@ static int write_graph_chunk_generation_data(struct hashfile *f,
 
 	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;
+		timestamp_t offset;
+		repo_parse_commit(ctx->r, c);
+		offset = commit_graph_data_at(c)->generation - c->date;
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
 		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
@@ -1444,15 +1446,20 @@ 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 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;
+		struct commit *c = ctx->commits.list[i];
+		uint32_t level;
+		timestamp_t corrected_commit_date;
+
+		repo_parse_commit(ctx->r, c);
+		level = *topo_level_slab_at(ctx->topo_levels, c);
+		corrected_commit_date = commit_graph_data_at(c)->generation;
 
 		display_progress(ctx->progress, i + 1);
 		if (level != GENERATION_NUMBER_ZERO &&
 		    corrected_commit_date != GENERATION_NUMBER_ZERO)
 			continue;
 
-		commit_list_insert(ctx->commits.list[i], &list);
+		commit_list_insert(c, &list);
 		while (list) {
 			struct commit *current = list->item;
 			struct commit_list *parent;
@@ -1461,6 +1468,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 			timestamp_t max_corrected_commit_date = 0;
 
 			for (parent = current->parents; parent; parent = parent->next) {
+				repo_parse_commit(ctx->r, parent->item);
 				level = *topo_level_slab_at(ctx->topo_levels, parent->item);
 				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
 
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index fa27df579a5..2cf29f425a0 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -446,6 +446,27 @@ test_expect_success 'warn on improper hash version' '
 	)
 '
 
+test_expect_failure 'lower layers have overflow chunk' '
+	cd "$TRASH_DIRECTORY/full" &&
+	UNIX_EPOCH_ZERO="@0 +0000" &&
+	FUTURE_DATE="@2147483646 +0000" &&
+	rm -f .git/objects/info/commit-graph &&
+	test_commit --date "$FUTURE_DATE" future-1 &&
+	test_commit --date "$UNIX_EPOCH_ZERO" old-1 &&
+	git commit-graph write --reachable &&
+	test_commit --date "$FUTURE_DATE" future-2 &&
+	test_commit --date "$UNIX_EPOCH_ZERO" old-2 &&
+	git commit-graph write --reachable --split=no-merge &&
+	test_commit extra &&
+	git commit-graph write --reachable --split=no-merge &&
+	git commit-graph write --reachable &&
+	graph_read_expect 16 "generation_data generation_data_overflow extra_edges" &&
+	mv .git/objects/info/commit-graph commit-graph-upgraded &&
+	git commit-graph write --reachable &&
+	graph_read_expect 16 "generation_data generation_data_overflow extra_edges" &&
+	test_cmp .git/objects/info/commit-graph commit-graph-upgraded
+'
+
 # the verify tests below expect the commit-graph to contain
 # exactly the commits reachable from the commits/8 branch.
 # If the file changes the set of commits in the list, then the
-- 
gitgitgadget

[PATCH v2 3/6] commit-graph: validate layers for generation data

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

We need to be extra careful that we don't use corrected
commit dates from any layer of a commit-graph chain if there is a
single commit-graph file that is missing the generation_data chunk.
Update validate_mixed_generation_chain() to correctly update each
layer to ignore the generation_data chunk in this case. It now also
returns 1 if all layers have a generation_data chunk. This return
value will be used in the next change.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 22 ++++++++++++++++------
 1 file changed, 16 insertions(+), 6 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index edbb3a0f2cc..b3f7c3bbcb3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -614,19 +614,29 @@ static struct commit_graph *load_commit_graph_chain(struct repository *r,
 	return graph_chain;
 }
 
-static void validate_mixed_generation_chain(struct commit_graph *g)
+/*
+ * returns 1 if and only if all graphs in the chain have
+ * corrected commit dates stored in the generation_data chunk.
+ */
+static int validate_mixed_generation_chain(struct commit_graph *g)
 {
-	int read_generation_data;
+	int read_generation_data = 1;
+	struct commit_graph *p = g;
 
-	if (!g)
-		return;
+	while (read_generation_data && p) {
+		read_generation_data = p->read_generation_data;
+		p = p->base_graph;
+	}
 
-	read_generation_data = !!g->chunk_generation_data;
+	if (read_generation_data)
+		return 1;
 
 	while (g) {
-		g->read_generation_data = read_generation_data;
+		g->read_generation_data = 0;
 		g = g->base_graph;
 	}
+
+	return 0;
 }
 
 struct commit_graph *read_commit_graph_one(struct repository *r,
-- 
gitgitgadget

[PATCH v2 4/6] commit-graph: compute generations separately

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

The compute_generation_numbers() method was introduced by 3258c663
(commit-graph: compute generation numbers, 2018-05-01) to compute what
is now known as "topological levels". These are still stored in the
commit-graph file for compatibility sake while c1a09119 (commit-graph:
implement corrected commit date, 2021-01-16) updated the method to also
compute the new version of generation numbers: corrected commit date.

It makes sense why these are grouped. They perform very similar walks of
the necessary commits and compute similar maximums over each parent.
However, having these two together conflates them in subtle ways that is
hard to separate.

In particular, the topo_level slab is used to store the topological
levels in all cases, but the commit_graph_data_at(c)->generation member
stores different values depending on the state of the existing
commit-graph file.

* If the existing commit-graph file has a "GDAT" chunk, then these
  values represent corrected commit dates.

* If the existing commit-graph file doesn't have a "GDAT" chunk, then
  these values are actually the topological levels.

This issue only occurs only when upgrading an existing commit-graph file
into one that has the "GDAT" chunk. The current change does not resolve
this upgrade problem, but splitting the implementation into two pieces
here helps with that process, which will follow in the next change.

The important thing this helps with is the case where the
num_generation_data_overflows was being incremented incorrectly,
triggering a write of the overflow chunk.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 70 ++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 56 insertions(+), 14 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index b3f7c3bbcb3..2790f70d113 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1446,27 +1446,24 @@ static void close_reachable(struct write_commit_graph_context *ctx)
 	stop_progress(&ctx->progress);
 }
 
-static void compute_generation_numbers(struct write_commit_graph_context *ctx)
+static void compute_topological_levels(struct write_commit_graph_context *ctx)
 {
 	int i;
 	struct commit_list *list = NULL;
 
 	if (ctx->report_progress)
 		ctx->progress = start_delayed_progress(
-					_("Computing commit graph generation numbers"),
+					_("Computing commit graph topological levels"),
 					ctx->commits.nr);
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];
 		uint32_t level;
-		timestamp_t corrected_commit_date;
 
 		repo_parse_commit(ctx->r, c);
 		level = *topo_level_slab_at(ctx->topo_levels, c);
-		corrected_commit_date = commit_graph_data_at(c)->generation;
 
 		display_progress(ctx->progress, i + 1);
-		if (level != GENERATION_NUMBER_ZERO &&
-		    corrected_commit_date != GENERATION_NUMBER_ZERO)
+		if (level != GENERATION_NUMBER_ZERO)
 			continue;
 
 		commit_list_insert(c, &list);
@@ -1475,15 +1472,12 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 			struct commit_list *parent;
 			int all_parents_computed = 1;
 			uint32_t max_level = 0;
-			timestamp_t max_corrected_commit_date = 0;
 
 			for (parent = current->parents; parent; parent = parent->next) {
 				repo_parse_commit(ctx->r, parent->item);
 				level = *topo_level_slab_at(ctx->topo_levels, parent->item);
-				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
 
-				if (level == GENERATION_NUMBER_ZERO ||
-				    corrected_commit_date == GENERATION_NUMBER_ZERO) {
+				if (level == GENERATION_NUMBER_ZERO) {
 					all_parents_computed = 0;
 					commit_list_insert(parent->item, &list);
 					break;
@@ -1491,9 +1485,6 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 
 				if (level > max_level)
 					max_level = level;
-
-				if (corrected_commit_date > max_corrected_commit_date)
-					max_corrected_commit_date = corrected_commit_date;
 			}
 
 			if (all_parents_computed) {
@@ -1502,6 +1493,55 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 				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;
+			}
+		}
+	}
+	stop_progress(&ctx->progress);
+}
+
+static void compute_generation_numbers(struct write_commit_graph_context *ctx)
+{
+	int i;
+	struct commit_list *list = NULL;
+
+	if (ctx->report_progress)
+		ctx->progress = start_delayed_progress(
+					_("Computing commit graph generation numbers"),
+					ctx->commits.nr);
+	for (i = 0; i < ctx->commits.nr; i++) {
+		struct commit *c = ctx->commits.list[i];
+		timestamp_t corrected_commit_date;
+
+		repo_parse_commit(ctx->r, c);
+		corrected_commit_date = commit_graph_data_at(c)->generation;
+
+		display_progress(ctx->progress, i + 1);
+		if (corrected_commit_date != GENERATION_NUMBER_ZERO)
+			continue;
+
+		commit_list_insert(c, &list);
+		while (list) {
+			struct commit *current = list->item;
+			struct commit_list *parent;
+			int all_parents_computed = 1;
+			timestamp_t max_corrected_commit_date = 0;
+
+			for (parent = current->parents; parent; parent = parent->next) {
+				repo_parse_commit(ctx->r, parent->item);
+				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
+
+				if (corrected_commit_date == GENERATION_NUMBER_ZERO) {
+					all_parents_computed = 0;
+					commit_list_insert(parent->item, &list);
+					break;
+				}
+
+				if (corrected_commit_date > max_corrected_commit_date)
+					max_corrected_commit_date = corrected_commit_date;
+			}
+
+			if (all_parents_computed) {
+				pop_commit(&list);
 
 				if (current->date && current->date > max_corrected_commit_date)
 					max_corrected_commit_date = current->date - 1;
@@ -2401,7 +2441,9 @@ int write_commit_graph(struct object_directory *odb,
 
 	validate_mixed_generation_chain(ctx->r->objects->commit_graph);
 
-	compute_generation_numbers(ctx);
+	compute_topological_levels(ctx);
+	if (ctx->write_generation_data)
+		compute_generation_numbers(ctx);
 
 	if (ctx->changed_paths)
 		compute_bloom_filters(ctx);
-- 
gitgitgadget

[PATCH v2 5/6] commit-graph: be extra careful about mixed generations

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

When upgrading to a commit-graph with corrected commit dates from
one without, there are a few things that need to be considered.

When computing generation numbers for the new commit-graph file that
expects to add the generation_data chunk with corrected commit
dates, we need to ensure that the 'generation' member of the
commit_graph_data struct is set to zero for these commits.

Unfortunately, the fallback to use topological level for generation
number when corrected commit dates are not available are causing us
harm here: parsing commits notices that read_generation_data is
false and populates 'generation' with the topological level.

The solution is to iterate through the commits, parse the commits
to populate initial values, then reset the generation values to
zero to trigger recalculation. This loop only occurs when the
existing commit-graph data has no corrected commit dates.

While this improves our situation somewhat, we have not completely
solved the issue for correctly computing generation numbers for mixed
layers. That follows in the next change.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c | 14 ++++++++++++--
 1 file changed, 12 insertions(+), 2 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index 2790f70d113..ee8d5a0cdb4 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1036,7 +1036,8 @@ struct write_commit_graph_context {
 		 split:1,
 		 changed_paths:1,
 		 order_by_pack:1,
-		 write_generation_data:1;
+		 write_generation_data:1,
+		 trust_generation_numbers:1;
 
 	struct topo_level_slab *topo_levels;
 	const struct commit_graph_opts *opts;
@@ -1508,6 +1509,15 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 		ctx->progress = start_delayed_progress(
 					_("Computing commit graph generation numbers"),
 					ctx->commits.nr);
+
+	if (!ctx->trust_generation_numbers) {
+		for (i = 0; i < ctx->commits.nr; i++) {
+			struct commit *c = ctx->commits.list[i];
+			repo_parse_commit(ctx->r, c);
+			commit_graph_data_at(c)->generation = GENERATION_NUMBER_ZERO;
+		}
+	}
+
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];
 		timestamp_t corrected_commit_date;
@@ -2439,7 +2449,7 @@ int write_commit_graph(struct object_directory *odb,
 	} else
 		ctx->num_commit_graphs_after = 1;
 
-	validate_mixed_generation_chain(ctx->r->objects->commit_graph);
+	ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
 
 	compute_topological_levels(ctx);
 	if (ctx->write_generation_data)
-- 
gitgitgadget

[PATCH v2 6/6] commit-graph: prepare commit graph

[Derrick Stolee via GitGitGadget]

From: Derrick Stolee <dstolee@microsoft.com>

Before checking if the repository has a commit-graph loaded, be sure
to run prepare_commit_graph(). This is necessary because otherwise
the topo_levels slab is not initialized. As we compute topo_levels for
the new commits, we iterate further into the lower layers since the
first visit to each commit looks as though the topo_level is not
populated.

By properly initializing the topo_slab, we fix the previously broken
case of a split commit graph where a base layer has the
generation_data_overflow chunk.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-graph.c          | 10 ++--------
 t/t5318-commit-graph.sh |  2 +-
 2 files changed, 3 insertions(+), 9 deletions(-)

diff --git a/commit-graph.c b/commit-graph.c
index ee8d5a0cdb4..94d3ab4a04f 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -2348,6 +2348,7 @@ int write_commit_graph(struct object_directory *odb,
 	init_topo_level_slab(&topo_levels);
 	ctx->topo_levels = &topo_levels;
 
+	prepare_commit_graph(ctx->r);
 	if (ctx->r->objects->commit_graph) {
 		struct commit_graph *g = ctx->r->objects->commit_graph;
 
@@ -2361,7 +2362,6 @@ int write_commit_graph(struct object_directory *odb,
 		ctx->changed_paths = 1;
 	if (!(flags & COMMIT_GRAPH_NO_WRITE_BLOOM_FILTERS)) {
 		struct commit_graph *g;
-		prepare_commit_graph_one(ctx->r, ctx->odb);
 
 		g = ctx->r->objects->commit_graph;
 
@@ -2373,10 +2373,7 @@ int write_commit_graph(struct object_directory *odb,
 	}
 
 	if (ctx->split) {
-		struct commit_graph *g;
-		prepare_commit_graph(ctx->r);
-
-		g = ctx->r->objects->commit_graph;
+		struct commit_graph *g = ctx->r->objects->commit_graph;
 
 		while (g) {
 			ctx->num_commit_graphs_before++;
@@ -2400,9 +2397,6 @@ int write_commit_graph(struct object_directory *odb,
 
 	ctx->approx_nr_objects = approximate_object_count();
 
-	if (ctx->append)
-		prepare_commit_graph_one(ctx->r, ctx->odb);
-
 	if (ctx->append && ctx->r->objects->commit_graph) {
 		struct commit_graph *g = ctx->r->objects->commit_graph;
 		for (i = 0; i < g->num_commits; i++) {
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index 2cf29f425a0..5b15f1aa0f6 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -446,7 +446,7 @@ test_expect_success 'warn on improper hash version' '
 	)
 '
 
-test_expect_failure 'lower layers have overflow chunk' '
+test_expect_success 'lower layers have overflow chunk' '
 	cd "$TRASH_DIRECTORY/full" &&
 	UNIX_EPOCH_ZERO="@0 +0000" &&
 	FUTURE_DATE="@2147483646 +0000" &&
-- 
gitgitgadget

Re: [PATCH v2 0/6] Generation Number v2: Fix a tricky split graph bug

[Taylor Blau]

On Tue, Feb 02, 2021 at 03:01:17AM +0000, Derrick Stolee via GitGitGadget wrote:
> Updates in v2
> =============
>
>  * Fixed some typos or other clarifications in commit messages.
>
>  * The loop assigning read_generation_data is skipped if they already all
>    agree with value 1.
>
>  * I split compute_generation_numbers into two methods. This essentially
>    splits the previous patch 4 into patches 4 & 5 here. The new patch 4 just
>    splits the logic as-is, then the new patch 5 does the re-initialization
>    of generation values when in the upgrade scenario.

Thanks for addressing my nits. I'm much happier with patch 5 as a result
of your changes, so I think this series was a positive step forward not
only for fixing a correctness bug, but also for improving the
readability of commit-graph.c.

Both the range-diff and the new patches look good to me, so this series
has my:

  Reviewed-by: Taylor Blau <me@ttaylorr.com>


Thanks,
Taylor

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Jonathan Nieder]

Derrick Stolee wrote:

> There is a subtle failure happening when computing corrected commit
> dates with --split enabled. It requires a base layer needing the
> generation_data_overflow chunk. Then, the next layer on top
> erroneously thinks it needs an overflow chunk due to a bug leading
> to recalculating all reachable generation numbers. The output of
> the failure is
>
>   BUG: commit-graph.c:1912: expected to write 8 bytes to
>   chunk 47444f56, but wrote 0 instead

At Google, we're running into a commit-graph issue that appears to
have also arrived as part of this last week's rollout.  This one is a
bit worse --- it is reproducible for affected users and stops them
from being able to do day-to-day development:

  $ git pull
  remote: Finding sources: 100% (33/33)
  remote: Total 33 (delta 18), reused 33 (delta 18)
  Unpacking objects: 100% (33/33), 27.44 KiB | 460.00 KiB/s, done.
  From https://example.com/path/to/repo
     05ba0d775..279e4e6d0  master     -> origin/master
  BUG: commit-reach.c:64: bad generation skip     29e3 >      628 at 62abdabd1be00ebadbf73061ecf72b35042338e3
  error: merge died of signal 6

"git commit-graph verify" agrees that the generation numbers are wrong:

  $ git commit-graph verify
  commit-graph generation for commit 4290b2214cdf50263118322735347d151715a272 is 3 != 1586
  Verifying commits in commit graph: 100% (1/1), done.
  commit-graph generation for commit b6c73a8472c7cb503cce0668849150a4b4329230 is 1576 != 10724
  Verifying commits in commit graph: 100% (10/10), done.
  Verifying commits in commit graph: 100% (88/88), done.
  Verifying commits in commit graph: 100% (208/208), done.
  Verifying commits in commit graph: 100% (592/592), done.
  Verifying commits in commit graph: 100% (1567/1567), done.
  Verifying commits in commit graph: 100% (8358/8358), done.

We have some examples of repositories that were corrupted this way,
but we didn't catch them in the act of corruption --- it started
happening to several users with this release so we immediately rolled
back.

Questions:

- is this likely to be due to the same cause, or is it orthogonal?

- what is the recommended way to recover from this state?  "git fsck"
  shows the repositories to have no problems.  "git help commit-graph"
  doesn't show a command for users to use; is
  `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
  command?

- is there configuration or a patch we can roll out to help affected
  users recover from this state?

Thanks,
Jonathan

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Derrick Stolee]

On 2/2/2021 8:08 PM, Jonathan Nieder wrote:
> Derrick Stolee wrote:
> 
>> There is a subtle failure happening when computing corrected commit
>> dates with --split enabled. It requires a base layer needing the
>> generation_data_overflow chunk. Then, the next layer on top
>> erroneously thinks it needs an overflow chunk due to a bug leading
>> to recalculating all reachable generation numbers. The output of
>> the failure is
>>
>>   BUG: commit-graph.c:1912: expected to write 8 bytes to
>>   chunk 47444f56, but wrote 0 instead
> 
> At Google, we're running into a commit-graph issue that appears to
> have also arrived as part of this last week's rollout.  This one is a
> bit worse --- it is reproducible for affected users and stops them
> from being able to do day-to-day development:

You're shipping 'next' widely? I appreciate the extra eyes on
early bits, so we can find more issues and get them resolved.

>   $ git pull
>   remote: Finding sources: 100% (33/33)
>   remote: Total 33 (delta 18), reused 33 (delta 18)
>   Unpacking objects: 100% (33/33), 27.44 KiB | 460.00 KiB/s, done.
>   From https://example.com/path/to/repo
>      05ba0d775..279e4e6d0  master     -> origin/master
>   BUG: commit-reach.c:64: bad generation skip     29e3 >      628 at 62abdabd1be00ebadbf73061ecf72b35042338e3
>   error: merge died of signal 6
> 
> "git commit-graph verify" agrees that the generation numbers are wrong:
> 
>   $ git commit-graph verify
>   commit-graph generation for commit 4290b2214cdf50263118322735347d151715a272 is 3 != 1586
>   Verifying commits in commit graph: 100% (1/1), done.
>   commit-graph generation for commit b6c73a8472c7cb503cce0668849150a4b4329230 is 1576 != 10724
>   Verifying commits in commit graph: 100% (10/10), done.
>   Verifying commits in commit graph: 100% (88/88), done.
>   Verifying commits in commit graph: 100% (208/208), done.
>   Verifying commits in commit graph: 100% (592/592), done.
>   Verifying commits in commit graph: 100% (1567/1567), done.
>   Verifying commits in commit graph: 100% (8358/8358), done.
> 
> We have some examples of repositories that were corrupted this way,
> but we didn't catch them in the act of corruption --- it started
> happening to several users with this release so we immediately rolled
> back.

It is definitely related to the split commit-graph during the
upgrade scenario. Your verify output shows that you are using
the --split option heavily (possibly with fetch.writeCommitGraph?
or are you using 'git maintenance run --task=commit-graph'?)

> Questions:
> 
> - is this likely to be due to the same cause, or is it orthogonal?

My guess is that the reason is the same. I think that you might
have some strangeness of a commit-graph layer with corrected commit
dates being below a commit-graph layer without it.

> - what is the recommended way to recover from this state?  "git fsck"
>   shows the repositories to have no problems.  "git help commit-graph"
>   doesn't show a command for users to use; is
>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
>   command?

That, followed by `git commit-graph write --reachable [--changed-paths]`
depending on what they want.

> - is there configuration or a patch we can roll out to help affected
>   users recover from this state?

If you are willing, then take v2 of this series and follow through by
clearing the commit-graph files of affected users. Note that you can
be proactive using `git commit-graph verify` to see who needs rewrites.

Thanks,
-Stolee

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Jonathan Nieder]

Hi,

Derrick Stolee wrote:
> On 2/2/2021 8:08 PM, Jonathan Nieder wrote:

>> At Google, we're running into a commit-graph issue that appears to
>> have also arrived as part of this last week's rollout.  This one is a
>> bit worse --- it is reproducible for affected users and stops them
>> from being able to do day-to-day development:
>
> You're shipping 'next' widely? I appreciate the extra eyes on
> early bits, so we can find more issues and get them resolved.

Yes.  Changes in 'next' have already gotten all the vetting via code
review that they're going to get; the difference between changes in
'next' and 'master' is that the latter have had some production
exposure among users of 'next' with the ability to get help from a
local expert, roll back quickly when there's a problem, and so on.  I
recommend that anyone with an installation with that ability use
'next', to improve the quality of code that ultimately is released
from 'master'.

It also helps us get the chance to use our experience to affect the
direction of a topic before it's too late.

[...]
>> We have some examples of repositories that were corrupted this way,
>> but we didn't catch them in the act of corruption --- it started
>> happening to several users with this release so we immediately rolled
>> back.
>
> It is definitely related to the split commit-graph during the
> upgrade scenario. Your verify output shows that you are using
> the --split option heavily (possibly with fetch.writeCommitGraph?
> or are you using 'git maintenance run --task=commit-graph'?)

Yep, the splits come from fetch.writeCommitGraph.

[...]
>> - what is the recommended way to recover from this state?  "git fsck"
>>   shows the repositories to have no problems.  "git help commit-graph"
>>   doesn't show a command for users to use; is
>>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
>>   command?
>
> That, followed by `git commit-graph write --reachable [--changed-paths]`
> depending on what they want.

Can we package this as something more user-friendly?  E.g.

	git commit-graph clear
	git commit-graph write --reachable

If that makes sense to you, I'm happy to send a patch (or to review
one if someone else gets to it first).  I'm mostly asking to find out
whether this matches your idea of what the UI should be like.

>> - is there configuration or a patch we can roll out to help affected
>>   users recover from this state?
>
> If you are willing, then take v2 of this series and follow through by
> clearing the commit-graph files of affected users. Note that you can
> be proactive using `git commit-graph verify` to see who needs rewrites.

Does this mean we should change the BUG error message to help affected
users discover how they can recover for themselves (for example, using
commands like the above)?

Also, should "git fsck" call "git commit-graph verify" to make the
latter more discoverable?

Thanks,
Jonathan

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

>> - what is the recommended way to recover from this state?  "git fsck"
>>   shows the repositories to have no problems.  "git help commit-graph"
>>   doesn't show a command for users to use; is
>>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
>>   command?

"rm -f .git/objects/info/commit-graph" as well, no?

> That, followed by `git commit-graph write --reachable [--changed-paths]`
> depending on what they want.

Just out of curiosity, how important is "--reachable"?  It only
traverses from the tips of refs and unlike fsck and repack, not from
reflog entries (or the index for that matter, but that shouldn't
make much difference as there is no _commit_ in the index).

>> - is there configuration or a patch we can roll out to help affected
>>   users recover from this state?
>
> If you are willing, then take v2 of this series and follow through by
> clearing the commit-graph files of affected users. Note that you can
> be proactive using `git commit-graph verify` to see who needs rewrites.

FYI, today's 368b6599 (Merge branch 'ds/commit-graph-genno-fix' into
jch, 2021-02-01) has this stuff.

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Derrick Stolee]

On 2/2/2021 8:48 PM, Jonathan Nieder wrote:
> Hi,
> 
> Derrick Stolee wrote:
>> On 2/2/2021 8:08 PM, Jonathan Nieder wrote:
> 
>>> At Google, we're running into a commit-graph issue that appears to
>>> have also arrived as part of this last week's rollout.  This one is a
>>> bit worse --- it is reproducible for affected users and stops them
>>> from being able to do day-to-day development:
>>
>> You're shipping 'next' widely? I appreciate the extra eyes on
>> early bits, so we can find more issues and get them resolved.
> 
> Yes.  Changes in 'next' have already gotten all the vetting via code
> review that they're going to get; the difference between changes in
> 'next' and 'master' is that the latter have had some production
> exposure among users of 'next' with the ability to get help from a
> local expert, roll back quickly when there's a problem, and so on.  I
> recommend that anyone with an installation with that ability use
> 'next', to improve the quality of code that ultimately is released
> from 'master'.
> 
> It also helps us get the chance to use our experience to affect the
> direction of a topic before it's too late.

This is a good practice. It's also how I found the issues fixed
in this series, but that's because I install it locally for my own
extra additional testing before shipping it to users.

> [...]
>>> We have some examples of repositories that were corrupted this way,
>>> but we didn't catch them in the act of corruption --- it started
>>> happening to several users with this release so we immediately rolled
>>> back.
>>
>> It is definitely related to the split commit-graph during the
>> upgrade scenario. Your verify output shows that you are using
>> the --split option heavily (possibly with fetch.writeCommitGraph?
>> or are you using 'git maintenance run --task=commit-graph'?)
> 
> Yep, the splits come from fetch.writeCommitGraph.
> 
> [...]
>>> - what is the recommended way to recover from this state?  "git fsck"
>>>   shows the repositories to have no problems.  "git help commit-graph"
>>>   doesn't show a command for users to use; is
>>>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
>>>   command?
>>
>> That, followed by `git commit-graph write --reachable [--changed-paths]`
>> depending on what they want.
> 
> Can we package this as something more user-friendly?  E.g.
> 
> 	git commit-graph clear
> 	git commit-graph write --reachable
> 
> If that makes sense to you, I'm happy to send a patch (or to review
> one if someone else gets to it first).  I'm mostly asking to find out
> whether this matches your idea of what the UI should be like.

'clear' is probably fine. I was thinking it might be good to have
an option to the 'write' subcommand to clear the existing data, but
it's probably better as separate steps.

>>> - is there configuration or a patch we can roll out to help affected
>>>   users recover from this state?
>>
>> If you are willing, then take v2 of this series and follow through by
>> clearing the commit-graph files of affected users. Note that you can
>> be proactive using `git commit-graph verify` to see who needs rewrites.
> 
> Does this mean we should change the BUG error message to help affected
> users discover how they can recover for themselves (for example, using
> commands like the above)?

It _is_ a bug that led to this, but it's more about incorrect
commit-graph data which could be caused by anything. Better to
have a better message such as "your commit-graph file is
probably corrupt".

> Also, should "git fsck" call "git commit-graph verify" to make the
> latter more discoverable?

Yes. I thought it did, but I must be incorrect.

Thanks,
-Stolee

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Derrick Stolee]

On 2/2/2021 9:06 PM, Junio C Hamano wrote:
> Derrick Stolee <stolee@gmail.com> writes:
> 
>>> - what is the recommended way to recover from this state?  "git fsck"
>>>   shows the repositories to have no problems.  "git help commit-graph"
>>>   doesn't show a command for users to use; is
>>>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
>>>   command?
> 
> "rm -f .git/objects/info/commit-graph" as well, no?

In this case, that won't be necessary since they are using a
split commit-graph. However, the following is what I do to
be extra sure:

	rm -rf .git/objects/info/commit-graph*

Deletes the singleton file and the directory.

>> That, followed by `git commit-graph write --reachable [--changed-paths]`
>> depending on what they want.
> 
> Just out of curiosity, how important is "--reachable"?  It only
> traverses from the tips of refs and unlike fsck and repack, not from
> reflog entries (or the index for that matter, but that shouldn't
> make much difference as there is no _commit_ in the index).

I just like to focus on the reachable commits starting at refs
instead of scanning all packed objects to see which are commits
or not.

Thanks,
-stolee

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Taylor Blau]

On Tue, Feb 02, 2021 at 10:07:32PM -0500, Derrick Stolee wrote:
> > Can we package this as something more user-friendly?  E.g.
> >
> > 	git commit-graph clear
> > 	git commit-graph write --reachable
> >
> > If that makes sense to you, I'm happy to send a patch (or to review
> > one if someone else gets to it first).  I'm mostly asking to find out
> > whether this matches your idea of what the UI should be like.
>
> 'clear' is probably fine. I was thinking it might be good to have
> an option to the 'write' subcommand to clear the existing data, but
> it's probably better as separate steps.

Wouldn't 'git commit-graph write --split=replace --reachable' do the
same thing? I know that you changed some of the spots where we load an
existing commit graph, so my claim might be out-of-date, but I'm pretty
sure that this would get you out of a broken state.

Thinking aloud, I'm not totally sure that we should be exposing "git
commit-graph clear" to users. The only time that you'd want to run this
is if you were trying to remove a corrupted commit-graph, so I'd rather
see guidance on how to do that safely show up in
Documentation/git-commit-graph.txt.

On the other hand, now I'm encouraging running "rm -fr
$GIT_DIR/objects/info/commit-graph*", which feels dangerous.

Somewhere in the middle would be something like:

  git -c core.commitGraph=false commit-graph write --reachable

which would disable reading existing commit-graph files. Since
85102ac71b (commit-graph: don't write commit-graph when disabled,
2020-10-09), that causes us to exit immediately.

I think that reverting that patch and advertising setting
'core.commitGraph=false' in the documentation makes the most sense.

Thanks,
Taylor

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Eric Sunshine]

On Wed, Feb 3, 2021 at 10:55 AM Taylor Blau <me@ttaylorr.com> wrote:
> On Tue, Feb 02, 2021 at 10:07:32PM -0500, Derrick Stolee wrote:
> > 'clear' is probably fine. I was thinking it might be good to have
> > an option to the 'write' subcommand to clear the existing data, but
> > it's probably better as separate steps.
>
> Wouldn't 'git commit-graph write --split=replace --reachable' do the
> same thing? I know that you changed some of the spots where we load an
> existing commit graph, so my claim might be out-of-date, but I'm pretty
> sure that this would get you out of a broken state.
>
> Thinking aloud, I'm not totally sure that we should be exposing "git
> commit-graph clear" to users. The only time that you'd want to run this
> is if you were trying to remove a corrupted commit-graph, so I'd rather
> see guidance on how to do that safely show up in
> Documentation/git-commit-graph.txt.

Throwing one more idea into the mix, git-worktree recently got a
`repair` subcommand. Even though it presently repairs a small set of
problems, the subcommand name is intentionally generic so as to
provide room for growth. One could imagine `git commit-graph repair`
being added to provide a user-friendly mechanism for recovering from
commit-graph damage.

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> Thinking aloud, I'm not totally sure that we should be exposing "git
> commit-graph clear" to users. The only time that you'd want to run this
> is if you were trying to remove a corrupted commit-graph, so I'd rather
> see guidance on how to do that safely show up in
> Documentation/git-commit-graph.txt.
>
> On the other hand, now I'm encouraging running "rm -fr
> $GIT_DIR/objects/info/commit-graph*", which feels dangerous.

True.

As this is, like pack .idx file, supposed to be "precomputed cached
data that can be fully recreated using primary information" [*], I
am perfectly fine to say "commit-graph may have unexplored corners,
and when you hit a BUG(), you can safely use 'commit-graph clear'
and recreate it from scratch, or operate without it if you feel you
do not yet want to trust your data to it for now."  Giving safer and
easier way to opt out for those who need to get today's release
done, with enough performance incentive to re-enable it when the
crunch is over, would be an honest thing to do, I would think.

	Side note: the index file also used to be considered to hold
	such cached data, that can be recreated from the working
	tree data and the tip commit.  We no longer treat it that
	way, though.

> Somewhere in the middle would be something like:
>
>   git -c core.commitGraph=false commit-graph write --reachable

I am a bit worried about the thinking along this line, because it
gives the users an impression that there is no escaping from
trusting commit-graph---the one that was created from scratch is
bug-free and they only need to be cautious about incrementals.

But (1) we do not know that, and (2) it is an unconvincing message
to somebody who just got hit by a BUG().

> which would disable reading existing commit-graph files. Since
> 85102ac71b (commit-graph: don't write commit-graph when disabled,
> 2020-10-09), that causes us to exit immediately.

Meaning the three command sequence

	git commit-graph clear
	git commit-graph write --reachable
        git config core.commitGraph false

to force a clean build of a graph and forbid further updates until
the bug is squashed???  But should't core.commitGraph forbid reading
and using the data in the existing files, too?  In which case, shouldn't
it be equivalent to "git commit-graph clear"?

> I think that reverting that patch and advertising setting
> 'core.commitGraph=false' in the documentation makes the most sense.

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Taylor Blau]

On Wed, Feb 03, 2021 at 10:41:08AM -0800, Junio C Hamano wrote:
> Taylor Blau <me@ttaylorr.com> writes:
>
> > Thinking aloud, I'm not totally sure that we should be exposing "git
> > commit-graph clear" to users. The only time that you'd want to run this
> > is if you were trying to remove a corrupted commit-graph, so I'd rather
> > see guidance on how to do that safely show up in
> > Documentation/git-commit-graph.txt.
> >
> > On the other hand, now I'm encouraging running "rm -fr
> > $GIT_DIR/objects/info/commit-graph*", which feels dangerous.
>
> True.
>
> As this is, like pack .idx file, supposed to be "precomputed cached
> data that can be fully recreated using primary information" [*], I
> am perfectly fine to say "commit-graph may have unexplored corners,
> and when you hit a BUG(), you can safely use 'commit-graph clear'
> and recreate it from scratch, or operate without it if you feel you
> do not yet want to trust your data to it for now."  Giving safer and
> easier way to opt out for those who need to get today's release
> done, with enough performance incentive to re-enable it when the
> crunch is over, would be an honest thing to do, I would think.
>
> 	Side note: the index file also used to be considered to hold
> 	such cached data, that can be recreated from the working
> 	tree data and the tip commit.  We no longer treat it that
> 	way, though.
>
> > Somewhere in the middle would be something like:
> >
> >   git -c core.commitGraph=false commit-graph write --reachable
>
> I am a bit worried about the thinking along this line, because it
> gives the users an impression that there is no escaping from
> trusting commit-graph---the one that was created from scratch is
> bug-free and they only need to be cautious about incrementals.
>
> But (1) we do not know that, and (2) it is an unconvincing message
> to somebody who just got hit by a BUG().

This is a convincing counter-point to my proposal. Yeah, I agree that we
shouldn't be advertising that commit-graph is completely trustworthy.

> > which would disable reading existing commit-graph files. Since
> > 85102ac71b (commit-graph: don't write commit-graph when disabled,
> > 2020-10-09), that causes us to exit immediately.
>
> Meaning the three command sequence
>
> 	git commit-graph clear
> 	git commit-graph write --reachable
>         git config core.commitGraph false
>
> to force a clean build of a graph and forbid further updates until
> the bug is squashed???  But should't core.commitGraph forbid reading
> and using the data in the existing files, too?  In which case, shouldn't
> it be equivalent to "git commit-graph clear"?

I think we may be saying the same thing. I was suggesting that if we
reverted 85102ac71b, that 'git -c core.commitGraph=false commit-graph
write ...' would rewrite your commit-graph from scratch (without opening
up existing ones and propagating corruption).

So I was saying that that *would* be a viable "git commit-grpah clear"
(if 85102ac71b were reverted).

Thanks,
Taylor

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[SZEDER Gábor]

On Tue, Feb 02, 2021 at 06:06:51PM -0800, Junio C Hamano wrote:
> Derrick Stolee <stolee@gmail.com> writes:
> 
> >> - what is the recommended way to recover from this state?  "git fsck"
> >>   shows the repositories to have no problems.  "git help commit-graph"
> >>   doesn't show a command for users to use; is
> >>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
> >>   command?
> 
> "rm -f .git/objects/info/commit-graph" as well, no?
> 
> > That, followed by `git commit-graph write --reachable [--changed-paths]`
> > depending on what they want.
> 
> Just out of curiosity, how important is "--reachable"?  It only
> traverses from the tips of refs and unlike fsck and repack, not from
> reflog entries (or the index for that matter, but that shouldn't
> make much difference as there is no _commit_ in the index).

Scanning all objects in all packfiles is a very inefficient way to
find the commits to be recorded in the commit-graph, and depending on
the repository's shape and size can have several times higher runtime
and memory footprint.

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Junio C Hamano]

SZEDER Gábor <szeder.dev@gmail.com> writes:

> On Tue, Feb 02, 2021 at 06:06:51PM -0800, Junio C Hamano wrote:
>> Derrick Stolee <stolee@gmail.com> writes:
>> 
>> >> - what is the recommended way to recover from this state?  "git fsck"
>> >>   shows the repositories to have no problems.  "git help commit-graph"
>> >>   doesn't show a command for users to use; is
>> >>   `rm -fr .git/objects/info/commit-graphs/` the recommended recovery
>> >>   command?
>> 
>> "rm -f .git/objects/info/commit-graph" as well, no?
>> 
>> > That, followed by `git commit-graph write --reachable [--changed-paths]`
>> > depending on what they want.
>> 
>> Just out of curiosity, how important is "--reachable"?  It only
>> traverses from the tips of refs and unlike fsck and repack, not from
>> reflog entries (or the index for that matter, but that shouldn't
>> make much difference as there is no _commit_ in the index).
>
> Scanning all objects in all packfiles is a very inefficient way to
> find the commits to be recorded in the commit-graph, and depending on
> the repository's shape and size can have several times higher runtime
> and memory footprint.

But wouldn't it make the resulting graph file not very useful for
the purpose of say deciding what object to pack when running "gc" or
"repack" or "prune"?  The fact that it ignores the index and the reflog
entries as roots of traversal with "--reachable" bothers me.

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Derrick Stolee]

On 2/7/2021 3:12 PM, Junio C Hamano wrote:
> SZEDER Gábor <szeder.dev@gmail.com> writes:
>> Scanning all objects in all packfiles is a very inefficient way to
>> find the commits to be recorded in the commit-graph, and depending on
>> the repository's shape and size can have several times higher runtime
>> and memory footprint.
> 
> But wouldn't it make the resulting graph file not very useful for
> the purpose of say deciding what object to pack when running "gc" or
> "repack" or "prune"?  The fact that it ignores the index and the reflog
> entries as roots of traversal with "--reachable" bothers me.

The reflog _might_ have something of value there, but the hope is
that very few commits are actually being force-pushed away. The focus
is to prioritize the deep history, and it would definitely be an
anti-pattern if the commits in the reflog are so numerous that they
must be tracked by the commit-graph. Of course, skipping the --reachable
option enables a way to gather these commits as necessary.

The index won't have commit oids that matter (yes, for submodules they
will exist, but those are not commits for the super repo).

Thanks,
-Stolee

Re: [PATCH v2 2/6] commit-graph: always parse before commit_graph_data_at()

[Junio C Hamano]

Derrick Stolee <stolee@gmail.com> writes:

> The reflog _might_ have something of value there, but the hope is
> that very few commits are actually being force-pushed away. The focus
> is to prioritize the deep history, and it would definitely be an
> anti-pattern if the commits in the reflog are so numerous that they
> must be tracked by the commit-graph. Of course, skipping the --reachable
> option enables a way to gather these commits as necessary.

Sure.  As long as gaps in commit-graph coverage only affect
performance and never correctness (e.g. even if the things that are
only reachable from reflog entries are not covered by commit-graph,
when 'git prune' wants to know if an object can safely pruned, we
will correctly say "no, do not prune it yet"), that is perfectly fine.

Re: [PATCH v2 0/6] Generation Number v2: Fix a tricky split graph bug

[Abhishek Kumar]

On Tue, Feb 02, 2021 at 03:01:17AM +0000, Derrick Stolee via GitGitGadget wrote:
> Here is a bugfix for the recently-landed-in-next generation v2 topic
> (ak/corrected-commit-date).
> 
> This was occasionally hitting us when computing new commit-graphs on
> existing repositories with the new bits. It was very hard to reproduce, and
> it turns out to be due to not parsing commits before accessing generation
> number data. Doing so in the right place demonstrates the bug of recomputing
> the corrected commit date even for commits in lower layers with computed
> values.
> 
> The fix is split into these steps:
> 
>  1. Parse commits more often before accessing their data. (This allows the
>     bug to be demonstrated in the test suite.)
>  2. Check the full commit-graph chain for generation data chunks.
>  3. Don't compute corrected commit dates if the lower layers do not support
>     them.
>  4. Parse the commit-graph file more often.
> 
> Thanks, -Stolee
> 

Thanks for the fast bug-fix. It must have been hard to track down why as
we weren't able to reproduce this behaviour before. As Taylor said
before, this patch is a clear improvement in readability and correctness.

Thanks
- Abhishek

> 
> Updates in v2
> =============
> 
>  * Fixed some typos or other clarifications in commit messages.
> 
>  * The loop assigning read_generation_data is skipped if they already all
>    agree with value 1.
> 
>  * I split compute_generation_numbers into two methods. This essentially
>    splits the previous patch 4 into patches 4 & 5 here. The new patch 4 just
>    splits the logic as-is, then the new patch 5 does the re-initialization
>    of generation values when in the upgrade scenario.
> 
> Derrick Stolee (6):
>   commit-graph: use repo_parse_commit
>   commit-graph: always parse before commit_graph_data_at()
>   commit-graph: validate layers for generation data
>   commit-graph: compute generations separately
>   commit-graph: be extra careful about mixed generations
>   commit-graph: prepare commit graph
> 
>  commit-graph.c          | 138 +++++++++++++++++++++++++++++-----------
>  commit.h                |   5 +-
>  t/t5318-commit-graph.sh |  21 ++++++
>  3 files changed, 125 insertions(+), 39 deletions(-)
> 
> 
> base-commit: 5a3b130cad0d5c770f766e3af6d32b41766374c0
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-850%2Fderrickstolee%2Fgen-v2-upgrade-fix-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-850/derrickstolee/gen-v2-upgrade-fix-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/850
> 
> Range-diff vs v1:
> 
>  1:  9c605c99f66 = 1:  9c605c99f66 commit-graph: use repo_parse_commit
>  2:  82afa811dff ! 2:  454b183b9ba commit-graph: always parse before commit_graph_data_at()
>      @@ Commit message
>           problems when writing a commit-graph with corrected commit dates based
>           on a commit-graph without them.
>       
>      -    It has been difficult to identify the issue here becaus it was so hard
>      +    It has been difficult to identify the issue here because it was so hard
>           to reproduce. It relies on this uninitialized data having a non-zero
>           value, but also on specifically in a way that overwrites the existing
>           data.
>  3:  d554fa30660 ! 3:  3d223fa2156 commit-graph: validate layers for generation data
>      @@ commit-graph.c: static struct commit_graph *load_commit_graph_chain(struct repos
>        
>       -	if (!g)
>       -		return;
>      --
>      --	read_generation_data = !!g->chunk_generation_data;
>       +	while (read_generation_data && p) {
>       +		read_generation_data = p->read_generation_data;
>       +		p = p->base_graph;
>       +	}
>        
>      +-	read_generation_data = !!g->chunk_generation_data;
>      ++	if (read_generation_data)
>      ++		return 1;
>      + 
>        	while (g) {
>      - 		g->read_generation_data = read_generation_data;
>      +-		g->read_generation_data = read_generation_data;
>      ++		g->read_generation_data = 0;
>        		g = g->base_graph;
>        	}
>       +
>      -+	return read_generation_data;
>      ++	return 0;
>        }
>        
>        struct commit_graph *read_commit_graph_one(struct repository *r,
>  -:  ----------- > 4:  05248ff222f commit-graph: compute generations separately
>  4:  b267a9653a7 ! 5:  9bccee8fb63 commit-graph: be extra careful about mixed generations
>      @@ Commit message
>           existing commit-graph data has no corrected commit dates.
>       
>           While this improves our situation somewhat, we have not completely
>      -    solved the issue for correctly computing generation numbers for mixes
>      +    solved the issue for correctly computing generation numbers for mixed
>           layers. That follows in the next change.
>       
>           Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>      @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
>        					_("Computing commit graph generation numbers"),
>        					ctx->commits.nr);
>       +
>      -+	if (ctx->write_generation_data && !ctx->trust_generation_numbers) {
>      ++	if (!ctx->trust_generation_numbers) {
>       +		for (i = 0; i < ctx->commits.nr; i++) {
>       +			struct commit *c = ctx->commits.list[i];
>       +			repo_parse_commit(ctx->r, c);
>      @@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph
>       +
>        	for (i = 0; i < ctx->commits.nr; i++) {
>        		struct commit *c = ctx->commits.list[i];
>      - 		uint32_t level;
>      -@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>      - 				corrected_commit_date = commit_graph_data_at(parent->item)->generation;
>      - 
>      - 				if (level == GENERATION_NUMBER_ZERO ||
>      --				    corrected_commit_date == GENERATION_NUMBER_ZERO) {
>      -+				    (ctx->write_generation_data &&
>      -+				     corrected_commit_date == GENERATION_NUMBER_ZERO)) {
>      - 					all_parents_computed = 0;
>      - 					commit_list_insert(parent->item, &list);
>      - 					break;
>      -@@ commit-graph.c: static void compute_generation_numbers(struct write_commit_graph_context *ctx)
>      - 					max_level = GENERATION_NUMBER_V1_MAX - 1;
>      - 				*topo_level_slab_at(ctx->topo_levels, current) = max_level + 1;
>      - 
>      --				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++;
>      -+				if (ctx->write_generation_data) {
>      -+					timestamp_t cur_g;
>      -+					if (current->date && current->date > max_corrected_commit_date)
>      -+						max_corrected_commit_date = current->date - 1;
>      -+					cur_g = commit_graph_data_at(current)->generation
>      -+					      = max_corrected_commit_date + 1;
>      -+					if (cur_g - current->date > GENERATION_NUMBER_V2_OFFSET_MAX)
>      -+						ctx->num_generation_data_overflows++;
>      -+				}
>      - 			}
>      - 		}
>      - 	}
>      + 		timestamp_t corrected_commit_date;
>       @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
>        	} else
>        		ctx->num_commit_graphs_after = 1;
>      @@ commit-graph.c: int write_commit_graph(struct object_directory *odb,
>       -	validate_mixed_generation_chain(ctx->r->objects->commit_graph);
>       +	ctx->trust_generation_numbers = validate_mixed_generation_chain(ctx->r->objects->commit_graph);
>        
>      - 	compute_generation_numbers(ctx);
>      - 
>      + 	compute_topological_levels(ctx);
>      + 	if (ctx->write_generation_data)
>  5:  dddeec30ebf ! 6:  38086c85b52 commit-graph: prepare commit graph
>      @@ Commit message
>           commit-graph: prepare commit graph
>       
>           Before checking if the repository has a commit-graph loaded, be sure
>      -    to run prepare_commit_graph(). This is necessary because without this
>      -    instance we would not initialize the topo_levels slab for each of the
>      -    struct commit_graphs in the chain before we start to parse the
>      -    commits. This leads to possibly recomputing the topological levels for
>      -    commits in lower layers even when we are adding a small number of
>      -    commits on top.
>      +    to run prepare_commit_graph(). This is necessary because otherwise
>      +    the topo_levels slab is not initialized. As we compute topo_levels for
>      +    the new commits, we iterate further into the lower layers since the
>      +    first visit to each commit looks as though the topo_level is not
>      +    populated.
>       
>           By properly initializing the topo_slab, we fix the previously broken
>           case of a split commit graph where a base layer has the
> 
> -- 
> gitgitgadget