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

commit-graph: return generation from memory

2023-03-20T19:17:33Z

The commit_graph_generation() method used to report a value of GENERATION_NUMBER_INFINITY if the commit_graph_data_slab had an instance for the given commit but the graph_pos indicated the commit was not in the commit-graph file. However, an upcoming change will introduce the ability to set generation values in-memory without writing the commit-graph file. Thus, we can no longer trust 'graph_pos' to indicate whether or not the generation member can be trusted. Instead, trust the 'generation' member if the commit has a value in the slab _and_ the 'generation' member is non-zero. Otherwise, treat it as GENERATION_NUMBER_INFINITY. This only makes a difference for a very old case for the commit-graph: the very first Git release to write commit-graph files wrote zeroes in the topological level positions. If we are parsing a commit-graph with all zeroes, those commits will now appear to have GENERATION_NUMBER_INFINITY (as if they were not parsed from the commit-graph). I attempted several variations to work around the need for providing an uninitialized 'generation' member, but this was the best one I found. It does require a change to a verification test in t5318 because it reports a different error than the one about non-zero generation numbers. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'sg/parse-options-subcommand'

2022-09-01T20:40:18Z

Introduce the "subcommand" mode to parse-options API and update the command line parser of Git commands with subcommands. * sg/parse-options-subcommand: (23 commits) remote: run "remote rm" argv through parse_options() maintenance: add parse-options boilerplate for subcommands pass subcommand "prefix" arguments to parse_options() builtin/worktree.c: let parse-options parse subcommands builtin/stash.c: let parse-options parse subcommands builtin/sparse-checkout.c: let parse-options parse subcommands builtin/remote.c: let parse-options parse subcommands builtin/reflog.c: let parse-options parse subcommands builtin/notes.c: let parse-options parse subcommands builtin/multi-pack-index.c: let parse-options parse subcommands builtin/hook.c: let parse-options parse subcommands builtin/gc.c: let parse-options parse 'git maintenance's subcommands builtin/commit-graph.c: let parse-options parse subcommands builtin/bundle.c: let parse-options parse subcommands parse-options: add support for parsing subcommands parse-options: drop leading space from '--git-completion-helper' output parse-options: clarify the limitations of PARSE_OPT_NODASH parse-options: PARSE_OPT_KEEP_UNKNOWN only applies to --options api-parse-options.txt: fix description of OPT_CMDMODE t0040-parse-options: test parse_options() with various 'parse_opt_flags' ...

builtin/commit-graph.c: let parse-options parse subcommands

2022-08-19T18:13:15Z

'git commit-graph' parses its subcommands with an if-else if statement. parse-options has just learned to parse subcommands, so let's use that facility instead, with the benefits of shorter code, handling missing or unknown subcommands, and listing subcommands for Bash completion. Note that the functions implementing each subcommand only accept the 'argc' and '**argv' parameters, so add a (unused) '*prefix' parameter to make them match the type expected by parse-options, and thus avoid casting function pointers. Signed-off-by: SZEDER Gábor Signed-off-by: Junio C Hamano

Merge branch 'tb/commit-graph-genv2-upgrade-fix'

2022-08-03T20:36:08Z

There was a bug in the codepath to upgrade generation information in commit-graph from v1 to v2 format, which has been corrected. * tb/commit-graph-genv2-upgrade-fix: commit-graph: fix corrupt upgrade from generation v1 to v2 commit-graph: introduce `repo_find_commit_pos_in_graph()` t5318: demonstrate commit-graph generation v2 corruption

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

tests: don't assume a .git/info for .git/info/grafts

2022-06-06T19:00:21Z

Change those tests that assumed that a .git/info directory would be created for them when writing .git/info/grafts to explicitly create the directory. Do this using the new "TEST_CREATE_REPO_NO_TEMPLATE" facility, and use "mkdir" instead of "mkdir -p" to assert that we don't have the .git/info already. An exception to this is the "with grafts" test in "t6001-rev-list-graft.sh". There we're modifying our ".git" state in a for-loop, in lieu of refactoring that more extensively let's use "mkdir -p" there. Signed-off-by: Ævar Arnfjörð Bjarmason 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