commit-graph: fix corruption during generation v2 upgrade

This brief series resolves a bug where a commit-graph would become corrupt when upgrading from generation number v1 to v2, as originally reported in [1].

Some speculation occurred as to what might be causing that bug in the thread beginning at [1], until the problem was explained in more detail by Will Chandler in [2].

The crux of the issue, as is described in [2] and [3], is that the commit_graph_data slab is reused for read and write operations involving the commit-graph, leading to situations where data computed in preparation of a write is clobbered by a read of existing data.

The first patch demonstrates the issue, and the second patch prepares to fix it by introducing a helper function. The crux of the issue is described and fixed in the third patch.

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

Taylor Blau (3):
t5318: demonstrate commit-graph generation v2 corruption
commit-graph: introduce repo_find_commit_pos_in_graph()
commit-graph: fix corrupt upgrade from generation v1 to v2

 bloom.c                 | 10 +++++-----
 commit-graph.c          | 12 +++++++++---
 commit-graph.h          | 15 +++++++++++++++
 t/t5318-commit-graph.sh | 27 +++++++++++++++++++++++++++
 4 files changed, 56 insertions(+), 8 deletions(-)

2.37.0.1.g1379af2e9d

When upgrading a commit-graph using generation v1 to one using generation v2, it is possible to force Git into a corrupt state where it (incorrectly) believes that a GDO2 chunk is necessary, *after* deciding not to write one.

This makes subsequent reads using the commit-graph produce the following error message:

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

Demonstrate this bug by increasing our test coverage to include a minimal example of upgrading a commit-graph from generation v1 to v2. The only notable components of this test are:

- The committer date of the commit is chosen carefully so that the offset underflows when computed using a v1 generation number, but would not overflow when using v2 generation numbers.

- The upgrade to generation number v2 must read in the v1 generation numbers, which we can do by passing --changed-paths, which will force the commit-graph internals to call fill_commit_graph_info().

A future patch will squash this bug.

---
 t/t5318-commit-graph.sh | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

index fbf0d64578..4d9f62f22d 100755
@@ -811,4 +811,31 @@ test_expect_success 'set up and verify repo with generation data overflow chunk'
 
 graph_git_behavior 'generation data overflow chunk repo' repo left right
 
+test_expect_failure 'overflow during generation version upgrade' '
+	git init overflow-v2-upgrade &&
+	(
+		cd overflow-v2-upgrade &&
+
+		# This commit will have a date at two seconds past the Epoch,
+		# and a (v1) generation number of 1, since it is a root commit.
+		#
+		# The offset will then be computed as 2-1, which will underflow
+		# to 2^31, which is greater than the v2 offset small limit of
+		# 2^31-1.
+		#
+		# This is sufficient to need a large offset table for the v2
+		# generation numbers.
+		test_commit --date "@2 +0000" base &&
+		git repack -d &&
+
+		# Test that upgrading from generation v1 to v2 correctly
+		# produces the overflow table.
+		git -c commitGraph.generationVersion=1 commit-graph write &&
+		git -c commitGraph.generationVersion=2 commit-graph write \
+			--changed-paths &&
+
+		git rev-list --all
+	)
+'
+
 test_done

2.37.0.1.g1379af2e9d

Low-level callers in systems that are adjacent to the commit-graph (like the changed-path Bloom filter code) could benefit from being able to call a function like parse_commit_in_graph() without modifying the corresponding commit slab data.

This is useful in contexts where that slab data is being used to prepare for an upcoming commit-graph write, where Git must be careful to avoid clobbering any of that data during a read operation.

Introduce a low-level variant of parse_commit_in_graph() which returns the graph position of a given commit only, without modifying any of the slab data.

---
 commit-graph.c | 12 +++++++++---
 commit-graph.h | 15 +++++++++++++++
 2 files changed, 24 insertions(+), 3 deletions(-)

index 92d4503336..1c34ae1ea4 100644
@@ -889,6 +889,14 @@ static int find_commit_pos_in_graph(struct commit *item, struct commit_graph *g,
 	}
 }
 
+int repo_find_commit_pos_in_graph(struct repository *r, struct commit *c,
+				  uint32_t *pos)
+{
+	if (!prepare_commit_graph(r))
+		return 0;
+	return find_commit_pos_in_graph(c, r->objects->commit_graph, pos);
+}
+
 struct commit *lookup_commit_in_graph(struct repository *repo, const struct object_id *id)
 {
 	struct commit *commit;

@@ -946,9 +954,7 @@ int parse_commit_in_graph(struct repository *r, struct commit *item)
 void load_commit_graph_info(struct repository *r, struct commit *item)
 {
 	uint32_t pos;
-	if (!prepare_commit_graph(r))
-		return;
-	if (find_commit_pos_in_graph(item, r->objects->commit_graph, &pos))
+	if (repo_find_commit_pos_in_graph(r, item, &pos))
 		fill_commit_graph_info(item, r->objects->commit_graph, pos);
 }
 

index 2e3ac35237..f23b9e9026 100644
@@ -40,6 +40,21 @@ int open_commit_graph(const char *graph_file, int *fd, struct stat *st);
  */
 int parse_commit_in_graph(struct repository *r, struct commit *item);
 
+/*
+ * Fills `*pos` with the graph position of `c`, and returns 1 if `c` is
+ * found in the commit-graph belonging to `r`, or 0 otherwise.
+ * Initializes the commit-graph belonging to `r` if it hasn't been
+ * already.
+ *
+ * Note: this is a low-level helper that does not alter any slab data
+ * associated with `c`. Useful in circumstances where the slab data is
+ * already being modified (e.g., writing the commit-graph itself).
+ *
+ * In most cases, callers should use `parse_commit_in_graph()` instead.
+ */
+int repo_find_commit_pos_in_graph(struct repository *r, struct commit *c,
+				  uint32_t *pos);
+
 /*
  * Look up the given commit ID in the commit-graph. This will only return a
  * commit if the ID exists both in the graph and in the object database such

2.37.0.1.g1379af2e9d

The previous commit demonstrates a bug where a commit-graph using generation v2 could enter a state where one of the GDA2 values has its most-significant bit set (indicating that its value should be read from the extended offset table in the GDO2 chunk) without having a GDO2 chunk to read from.

This results in the following error message being displayed to the caller:

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

This bug arises in the following scenario:

- We decide to write a commit-graph using generation number v2, and decide (correctly) that no GDO2 chunk is necessary (e.g., because all of the commiter date offsets are no larger than 2^31-1).

- The v2 generation numbers are stored in the ->generation member of the commit slab holding struct commit_graph_data's.

- Later on, load_commit_graph_info() is called, overwriting the v2 generation data in the aforementioned slab with any existing v1 generation data.

Then, when the commit-graph code goes to write the GDA2 chunk via write_graph_chunk_generation_data(), we use the overwritten generation v1 data in a place where we expect to use a v2 generation number:

    offset = commit_graph_data_at(c)->generation - c->date;

...because commit_graph_data_at(c)->generation used to hold the v2 generation data, but it was overwritten to contain the v1 generation number via load_commit_graph_info().

If the offset computation above overflows the v2 generation number max, then write_graph_chunk_generation_data() will update its count of large offsets and write the marker accordingly:

    if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
        offset = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW | num_generation_data_overflows;
        num_generation_data_overflows++;
    }

and reads will look for the GDO2 chunk containing the overflowing v2 generation number, *after* the commit-graph code decided that no such chunk was necessary.

The main problem is that the slab containing struct commit_graph_data has a dual purpose. It is used to hold data that we are about to write to disk while generating a commit-graph, as well as hold data that was read from an existing commit-graph.

When the two mix, namely when the result of reading the commit-graph has a side-effect that mixes poorly with an in-progress commit-graph write, we end up with corrupt data.

A complete fix might be to introduce a new slab that is used exclusively for writing, and gate access between the two slabs based on context provided by the caller (e.g., whether this computation is part of a "read" or "write" operation).

But a more minimal fix addresses the only known path which overwrites the slab data, which is compute_bloom_filters() -> get_or_compute_bloom_filter() -> load_commit_graph_info() -> fill_commit_graph_info() by avoiding the last call which clobbers the data altogether.

This path only needs to learn the graph position of a given commit so that it can be used in load_bloom_filter_from_graph(). By replacing the last steps of the above with one that records the graph position into a temporary variable which is then used to load the existing Bloom data, we eliminate the clobbering, removing the corruption.

---
 bloom.c                 | 10 +++++-----
 t/t5318-commit-graph.sh |  2 +-
 2 files changed, 6 insertions(+), 6 deletions(-)

index 5e297038bb..816f063dca 100644
@@ -30,10 +30,9 @@ static inline unsigned char get_bitmask(uint32_t pos)
 
 static int load_bloom_filter_from_graph(struct commit_graph *g,
 					struct bloom_filter *filter,
-					struct commit *c)
+					uint32_t graph_pos)
 {
 	uint32_t lex_pos, start_index, end_index;
-	uint32_t graph_pos = commit_graph_position(c);
 
 	while (graph_pos < g->num_commits_in_base)
 		g = g->base_graph;

@@ -203,9 +202,10 @@ struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 	filter = bloom_filter_slab_at(&bloom_filters, c);
 
 	if (!filter->data) {
-		load_commit_graph_info(r, c);
-		if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)
-			load_bloom_filter_from_graph(r->objects->commit_graph, filter, c);
+		uint32_t graph_pos;
+		if (repo_find_commit_pos_in_graph(r, c, &graph_pos))
+			load_bloom_filter_from_graph(r->objects->commit_graph,
+						     filter, graph_pos);
 	}
 
 	if (filter->data && filter->len)

index 4d9f62f22d..f5f0895631 100755
@@ -811,7 +811,7 @@ test_expect_success 'set up and verify repo with generation data overflow chunk'
 
 graph_git_behavior 'generation data overflow chunk repo' repo left right
 
-test_expect_failure 'overflow during generation version upgrade' '
+test_expect_success 'overflow during generation version upgrade' '
 	git init overflow-v2-upgrade &&
 	(
 		cd overflow-v2-upgrade &&

2.37.0.1.g1379af2e9d

Thanks. Do we know where this breaks? Applying [1/3] on Git 2.32, 2.34, and 2.35 seems to claim that "known breakage vanished".

With a script like:

--- >8 ---
#!/bin/sh

set -e

rm -fr repo
git init -q repo
cd repo

echo "x" >x
git add x
GIT_AUTHOR_DATE="@2 +0000" \
GIT_COMMITTER_DATE="@2 +0000" git commit -q -m "$(cat x)"

git repack -d -q

git.compile -c commitGraph.generationVersion=1 commit-graph write git.compile -c commitGraph.generationVersion=2 commit-graph write \
--changed-paths

git.compile rev-list --all
--- 8< ---

You can bisect it to 3b0199d4c3 (commit-graph: start parsing generation v2 (again), 2022-03-01), but only because that patch teaches Git to recognize the existence of the generation v2 chunks.

I suspect (but haven't confirmed) that it was probably broken before 3b0199d4c3. But such breakage wouldn't have mattered, since despite understanding generation v2, previous versions of Git never read those chunks, which would have masked over this bug.

Thanks,
Taylor

Thanks for finding a good test.

Thanks, all, for identifying the scenario that causes this breakage. It was frustrating that we had reports of corruption without knowing where it was coming from.

This solution looks like the best we can do right now, although it hints that some refactoring would be good to distinguish between "commits as read" and "commits to be written" during this upgrade phase. Something to think about, but not to block this fix.

Thanks,
-Stolee

Yes, absolutely. Thanks for catching it.

Junio: you may want to s/2-1/1-2 in this patch's message, or I can send you a replacement or reroll, whatever is easier.

Thanks,
Taylor

I've already done "rebase -i" to do so.

But for future reference, the easiest for me is if the author said, after saying "Thanks for catching it", "Will reroll after waiting for a bit to see if there are other comments". That way, I only have to edit the latest draft of "What's cooking" report to mark the topic to be expecting a reroll (which will prevent me from merging the topic down to 'next' prematurely by mistake) and forget about it, until I actually see the updated set of patches. It would be even easier if the updated set of patches said which topic it is meant to replace. That way, I can trust other reviewers about the details of the change between iterations and play a patch monkey, when I am short of time.

It is more work to (1) look at the message you are responding to and understand what "2 minus 1" vs "1 minus 2" being discussed is about, and (2) go one level up in the thread to find the line in the patch that was being discussed, and (3) run "rebase -i" and change "pick" to "edit" and (4) find the line in the file that was affected by the hunk in question and edit it. The worst part of it is I'd either have to do it right away before I forget, or mark the message unread so that I can revisit it when I have enough time.

Either way is fine, but a straight resend with two notices (one that says "will reroll", the other that says "this replaces topic X") is the easiest to handle for me.

Thanks.

Thanks very much.

Makes sense. I appreciate you clarifying it explicitly, I've wondered over the years what is easiest for you when fixing a trivial issue in a larger series.

I've tended to try and avoid resubmitting a whole series when there is just a typo hoping to avoid flooding the list with too many (mostly unchanged) messages. But that requires you to do more work to futz with the patches before they hit your tree, so I try not to do it too often.

In any case, I'll try to err more often on the side of resubmitting a series after acking the typo in the hopes it makes your life easier ;-).

Thanks,
Taylor