git/t/t5318-commit-graph.sh, branch v2.37.2

commit-graph: fix corrupt upgrade from generation v1 to v2

2022-07-15T23:51:39Z

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. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

t5318: demonstrate commit-graph generation v2 corruption

2022-07-15T23:51:38Z

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. Reported-by: Jeff King Reproduced-by: Will Chandler Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

commit-graph: start parsing generation v2 (again)

2022-03-01T20:15:06Z

The 'read_generation_data' member of 'struct commit_graph' was introduced by 1fdc383c5 (commit-graph: use generation v2 only if entire chain does, 2021-01-16). The intention was to avoid using corrected commit dates if not all layers of a commit-graph had that data stored. The logic in validate_mixed_generation_chain() at that point incorrectly initialized read_generation_data to 1 if and only if the tip commit-graph contained the Corrected Commit Date chunk. This was "fixed" in 448a39e65 (commit-graph: validate layers for generation data, 2021-02-02) to validate that read_generation_data was either non-zero for all layers, or it would set read_generation_data to zero for all layers. The problem here is that read_generation_data is not initialized to be non-zero anywhere! This change initializes read_generation_data immediately after the chunk is parsed, so each layer will have its value present as soon as possible. The read_generation_data member is used in fill_commit_graph_info() to determine if we should use the corrected commit date or the topological levels stored in the Commit Data chunk. Due to this bug, all previous versions of Git were defaulting to topological levels in all cases! This can be measured with some performance tests. Using the Linux kernel as a testbed, I generated a complete commit-graph containing corrected commit dates and tested the 'new' version against the previous, 'old' version. First, rev-list with --topo-order demonstrates a 26% improvement using corrected commit dates: hyperfine \ -n "old" "$OLD_GIT rev-list --topo-order -1000 v3.6" \ -n "new" "$NEW_GIT rev-list --topo-order -1000 v3.6" \ --warmup=10 Benchmark 1: old Time (mean ± σ): 57.1 ms ± 3.1 ms Range (min … max): 52.9 ms … 62.0 ms 55 runs Benchmark 2: new Time (mean ± σ): 45.5 ms ± 3.3 ms Range (min … max): 39.9 ms … 51.7 ms 59 runs Summary 'new' ran 1.26 ± 0.11 times faster than 'old' These performance improvements are due to the algorithmic improvements given by walking fewer commits due to the higher cutoffs from corrected commit dates. However, this comes at a cost. The additional I/O cost of parsing the corrected commit dates is visible in case of merge-base commands that do not reduce the overall number of walked commits. hyperfine \ -n "old" "$OLD_GIT merge-base v4.8 v4.9" \ -n "new" "$NEW_GIT merge-base v4.8 v4.9" \ --warmup=10 Benchmark 1: old Time (mean ± σ): 110.4 ms ± 6.4 ms Range (min … max): 96.0 ms … 118.3 ms 25 runs Benchmark 2: new Time (mean ± σ): 150.7 ms ± 1.1 ms Range (min … max): 149.3 ms … 153.4 ms 19 runs Summary 'old' ran 1.36 ± 0.08 times faster than 'new' Performance issues like this are what motivated 702110aac (commit-graph: use config to specify generation type, 2021-02-25). In the future, we could fix this performance problem by inserting the corrected commit date offsets into the Commit Date chunk instead of having that data in an extra chunk. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

commit-graph: fix ordering bug in generation numbers

2022-03-01T20:14:57Z

When computing the generation numbers for a commit-graph, we compute the corrected commit dates and then check if their offsets from the actual dates is too large to fit in the 32-bit Generation Data chunk. However, there is a problem with this approach: if we have parsed the generation data from the previous commit-graph, then we continue the loop because the corrected commit date is already computed. This causes an under-count in the number of overflow values. It is incorrect to add an increment to num_generation_data_overflows next to this 'continue' statement, because we might start double-counting commits that are computed because of the depth-first search walk from a commit with an earlier OID. Instead, iterate over the full commit list at the end, checking the offsets to see how many grow beyond the maximum value. Create a new t5328-commit-graph-64-bit-time.sh test script to handle special cases of testing 64-bit timestamps. This helps demonstrate this bug in more cases. It still won't hit all potential cases until the next change, which reenables reading generation numbers. Use the skip_all trick from 0a2bfccb9c8 (t0051: use "skip_all" under !MINGW in single-test file, 2022-02-04) to make the output clean when run on a 32-bit system. Helped-by: Ævar Arnfjörð Bjarmason Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

t5318: extract helpers to lib-commit-graph.sh

2022-03-01T20:09:55Z

The graph_git_behavior helper is useful for testing that certain Git commands behave the same when using the commit-graph and when not using the commit-graph. Extract it to a new lib-commit-graph.sh file for use in new test scripts that will split out from t5318. While doing this extraction, also extract graph_read_expect and the logic for priming the test_oid_cache. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

test-read-graph: include extra post-parse info

2022-03-01T20:09:55Z

It can be helpful to verify that the 'struct commit_graph' that results from parsing a commit-graph is correctly structured. The existence of different chunks is not enough to verify that all of the optional features are correctly enabled. Update 'test-tool read-graph' to output an "options:" line that includes information for different parts of the struct commit_graph. In particular, this change demonstrates that the read_generation_data option is never being enabled, which will be fixed in a later change. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

t5000-t5999: detect and signal failure within loop

2021-12-13T18:29:48Z

Failures within `for` and `while` loops can go unnoticed if not detected and signaled manually since the loop itself does not abort when a contained command fails, nor will a failure necessarily be detected when the loop finishes since the loop returns the exit code of the last command it ran on the final iteration, which may not be the command which failed. Therefore, detect and signal failures manually within loops using the idiom `|| return 1` (or `|| exit 1` within subshells). Signed-off-by: Eric Sunshine Reviewed-by: Elijah Newren Signed-off-by: Junio C Hamano

fsck: verify commit graph when implicitly enabled

2021-10-15T21:30:07Z

Change fsck to check the "core_commit_graph" variable set in "repo-settings.c" instead of reading the "core.commitGraph" variable. This fixes a bug where we wouldn't verify the commit-graph if the config key was missing. This bug was introduced in 31b1de6a09 (commit-graph: turn on commit-graph by default, 2019-08-13), where core.commitGraph was turned on by default. Add tests to "t5318-commit-graph.sh" to verify that fsck checks the commit-graph as expected for the 3 values of core.commitGraph. Also, disable GIT_TEST_COMMIT_GRAPH in t/t0410-partial-clone.sh because some test cases use fsck in ways that assume that commit-graph checking is disabled. Helped-by: Ævar Arnfjörð Bjarmason Signed-off-by: Glen Choo Signed-off-by: Junio C Hamano

Merge branch 'ab/ignore-replace-while-working-on-commit-graph' into gc/use-repo-settings

2021-10-15T21:30:00Z

* ab/ignore-replace-while-working-on-commit-graph: commit-graph: don't consider "replace" objects with "verify" commit-graph tests: fix another graph_git_two_modes() helper commit-graph tests: fix error-hiding graph_git_two_modes() helper

commit-graph: don't consider "replace" objects with "verify"

2021-10-15T16:21:30Z

Extend the code added in d6538246d3d (commit-graph: not compatible with replace objects, 2018-08-20) which ignored replace objects in the "write" command to ignore it in the "verify" command too. We can just move this assignment to the cmd_commit_graph(), it dispatches to "write" and "verify", and we're unlikely to ever get a sub-command that would like to consider replace refs. This will make tests added in eddc1f556cd (mktag tests: test update-ref and reachable fsck, 2021-06-17) pass in combination with the "GIT_TEST_COMMIT_GRAPH" mode added in 859fdc0c3cf (commit-graph: define GIT_TEST_COMMIT_GRAPH, 2018-08-29), except that mode is currently broken (but is being fixed concurrently). See the discussion starting at [1]. 1. https://lore.kernel.org/git/87wnmihswp.fsf@evledraar.gmail.com/ Signed-off-by: Ævar Arnfjörð Bjarmason Signed-off-by: Junio C Hamano