| Message ID | 20220323210803.1130790-1-jonathantanmy@google.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | commit-reach: do not parse and iterate minima | expand |
Jonathan Tan <jonathantanmy@google.com> writes: > When a commit is parsed, it pretends to have a different (possibly > empty) list of parents if there is graft information for that commit. > But there is a bug that could occur when a commit is parsed, the graft > information is updated (for example, when a shallow file is rewritten), > and the same commit is subsequently used: the parents of the commit do > not conform to the updated graft information, but the information at the > time of parsing. > > This is usually not an issue, as a commit is usually introduced into the > repository at the same time as its graft information. That means that > when we try to parse that commit, we already have its graft information. > > However, this is not the case when fetching with --update-shallow. In > post_assign_shallow() in shallow.c, a revision walk is done that also > parses commits at the shallow boundary before updating the shallow > information (and hence, the graft information). (This revision walk > needs to be done before the update because the nature of the update > depends on the outcome of the revision walk.) If we were to > revision-walk such a commit (at the shallow boundary), we would end up > trying and failing to parse its parents because its list of parents is > not empty (since it was parsed before there was any graft information > telling us to conceal its parents). This revision walk will happen if > the client has submodules, as it will revision-walk the fetched commits > to check for new submodules, triggering this bug. > > This revision walk in post_assign_shallow() actually does not need to go > beyond the shallow boundaries, so the solution is twofold: (1) do not > iterate beyond such commits, and (2) in doing so, we no longer need to > parse them, so do not parse them. This sounds quite tricky. In this case we may know which commit we need to avoid (re)parsing to avoid the bug, but would it always be the case? It feels almost like we want to unparse the commit objects when we clear the grafts information in the previous patch, doesn't it?
On 24/03/22 04.08, Jonathan Tan wrote: > However, this is not the case when fetching with --update-shallow. In > post_assign_shallow() in shallow.c, a revision walk is done that also > parses commits at the shallow boundary before updating the shallow > information (and hence, the graft information). (This revision walk > needs to be done before the update because the nature of the update > depends on the outcome of the revision walk.) If we were to > revision-walk such a commit (at the shallow boundary), we would end up > trying and failing to parse its parents because its list of parents is > not empty (since it was parsed before there was any graft information > telling us to conceal its parents). This revision walk will happen if > the client has submodules, as it will revision-walk the fetched commits > to check for new submodules, triggering this bug. > What about fetching with --deepen? Will "unintended" unshallowing with --update-shallow possibly happen if --update-shallow is used, as opposed to --depth/--deepen?
On 3/23/2022 7:30 PM, Junio C Hamano wrote: > Jonathan Tan <jonathantanmy@google.com> writes: > >> When a commit is parsed, it pretends to have a different (possibly >> empty) list of parents if there is graft information for that commit. >> But there is a bug that could occur when a commit is parsed, the graft >> information is updated (for example, when a shallow file is rewritten), >> and the same commit is subsequently used: the parents of the commit do >> not conform to the updated graft information, but the information at the >> time of parsing. >> >> This is usually not an issue, as a commit is usually introduced into the >> repository at the same time as its graft information. That means that >> when we try to parse that commit, we already have its graft information. >> >> However, this is not the case when fetching with --update-shallow. In >> post_assign_shallow() in shallow.c, a revision walk is done that also >> parses commits at the shallow boundary before updating the shallow >> information (and hence, the graft information). (This revision walk >> needs to be done before the update because the nature of the update >> depends on the outcome of the revision walk.) If we were to >> revision-walk such a commit (at the shallow boundary), we would end up >> trying and failing to parse its parents because its list of parents is >> not empty (since it was parsed before there was any graft information >> telling us to conceal its parents). This revision walk will happen if >> the client has submodules, as it will revision-walk the fetched commits >> to check for new submodules, triggering this bug. >> >> This revision walk in post_assign_shallow() actually does not need to go >> beyond the shallow boundaries, so the solution is twofold: (1) do not >> iterate beyond such commits, and (2) in doing so, we no longer need to >> parse them, so do not parse them. > > This sounds quite tricky. In this case we may know which commit we > need to avoid (re)parsing to avoid the bug, but would it always be > the case? It feels almost like we want to unparse the commit > objects when we clear the grafts information in the previous patch, > doesn't it? I agree that the adjustment to paint_down_to_common() is a bit too coupled to this scenario, when we should just trust our commits to be valid if they have been parsed. We should always be able to parse our parents. Finding this bug is interesting, but I agree with Junio that a better fix would be to "unparse" a commit when modifying its graft in any way. That will universally fix it for any potential future commit walks that might be hit due to future code changes. Thanks, -Stolee
On 3/23/2022 5:08 PM, Jonathan Tan wrote: > test_expect_success 'fetch --update-shallow' ' > + git init a-submodule && > + test_commit -C a-submodule foo && You add a submodule here so you can trigger the bug in this test, but... > test_expect_success 'fetch --update-shallow into a repo with submodules' ' > - git init a-submodule && > - test_commit -C a-submodule foo && This test was already named to be specific to submodules. The test names could probably use an update to describe what's really the difference between the two tests. Is there a reason we couldn't trigger the failure only in this second test, allowing us to still test --update-shallow when submodules are NOT present? Thanks, -Stolee
On Thu, Mar 24, 2022 at 11:27:34AM -0400, Derrick Stolee wrote: > > This sounds quite tricky. In this case we may know which commit we > > need to avoid (re)parsing to avoid the bug, but would it always be > > the case? It feels almost like we want to unparse the commit > > objects when we clear the grafts information in the previous patch, > > doesn't it? > > I agree that the adjustment to paint_down_to_common() is a bit too > coupled to this scenario, when we should just trust our commits to > be valid if they have been parsed. We should always be able to > parse our parents. > > Finding this bug is interesting, but I agree with Junio that a > better fix would be to "unparse" a commit when modifying its graft > in any way. That will universally fix it for any potential future > commit walks that might be hit due to future code changes. I agree completely with you both. This made me think of some of the difficulties we encountered back in ce16364e89 (commit.c: don't persist substituted parents when unshallowing, 2020-07-08), particularly: One way to fix this would be to reset the parsed object pool entirely (flushing the cache and thus preventing subsequent reads from modifying their parents) after unshallowing. That would produce a problem when callers have a now-stale reference to the old pool, and so this patch implements a different approach. if I can recall back to when that patch was written, I think the issue was that dumping the entire set of parsed objects caused us to have stale references in the commit-graph machinery. I'm not sure whether or not the same difficulties would be encountered here, though. The shallow stuff is so tricky to me... Thanks, Taylor
Derrick Stolee <derrickstolee@github.com> writes: > On 3/23/2022 7:30 PM, Junio C Hamano wrote: > > This sounds quite tricky. In this case we may know which commit we > > need to avoid (re)parsing to avoid the bug, but would it always be > > the case? It feels almost like we want to unparse the commit > > objects when we clear the grafts information in the previous patch, > > doesn't it? > > I agree that the adjustment to paint_down_to_common() is a bit too > coupled to this scenario, when we should just trust our commits to > be valid if they have been parsed. We should always be able to > parse our parents. Thanks for the comments from both of you. I think Stolee's comment squarely hits the relevant points: it is precisely this scenario (revision walk to remove unreachable shallow commits) that must be careful of what it parses, and we *must not* parse the shallow boundary commit's parents. I think that there are 2 questions. First, whether we should parse the shallow boundary commit's parents, and second, whether we should parse the shallow boundary commit itself. In the commit message, I only discussed the second (because that implies the first), but perhaps I should have discussed both. Anyway, the discussion: (a) Should we parse the shallow boundary commit's parents? I think the obvious answer is no, because the remote probably wouldn't have sent them. But the code currently does: in paint_down_to_common(), they are parsed before being added to the priority queue (and parsing is necessary because the priority queue requires their date). Incidentally, this results in an error message from repo_parse_commit_internal() being printed, but repo_in_merge_bases_many() swallows the error by not checking the return value (it only checks whether a certain commit has a certain flag, which is true by the time the failing parent parse occurs). So we should have some sort of one_is_at_min_generation anyway, at least so that we can prevent its parents from being parsed. (b) Should we parse the shallow boundary commit itself? If we don't care, then we should unparse commits when grafts are cleared. In this case, though, I think that it is the responsibility of the shallow code to be careful with what it does with the commits. It is performing operations on commits that it alone knows shallow information about (because the shallow information is still being checked and thus not yet written to the repo). As I wrote in the commit message (which is admittedly long and perhaps hard to understand), I think that in the typical case, we only have a commit when its graft information is already present, so we don't need to worry about graft information changing from under it. > Finding this bug is interesting, but I agree with Junio that a > better fix would be to "unparse" a commit when modifying its graft > in any way. That will universally fix it for any potential future > commit walks that might be hit due to future code changes. Unparsing also means that code can't rely on commits being already parsed, even if they would expect it to be true (for example, a commit in a priority queue would be expected to be parsed, since we would have needed the date for it to enter the queue in the first place), but maybe this is not a big problem in practice.
Bagas Sanjaya <bagasdotme@gmail.com> writes: > What about fetching with --deepen? > > Will "unintended" unshallowing with --update-shallow possibly happen > if --update-shallow is used, as opposed to --depth/--deepen? This does change the graft status, but from grafted to ungrafted, so instead of trying to read parents that are not there, we will not read parents that are there. Which is also a problem, but more difficult to demonstrate why it is a problem, I think.
Derrick Stolee <derrickstolee@github.com> writes: > On 3/23/2022 5:08 PM, Jonathan Tan wrote: > > test_expect_success 'fetch --update-shallow' ' > > + git init a-submodule && > > + test_commit -C a-submodule foo && > > You add a submodule here so you can trigger the bug in this test, but... > > > test_expect_success 'fetch --update-shallow into a repo with submodules' ' > > - git init a-submodule && > > - test_commit -C a-submodule foo && > > This test was already named to be specific to submodules. The test names > could probably use an update to describe what's really the difference > between the two tests. > > Is there a reason we couldn't trigger the failure only in this second > test, allowing us to still test --update-shallow when submodules are NOT > present? > > Thanks, > -Stolee I tried but somehow couldn't figure out the correct server and client state to trigger this. If I can't think of anything else, I might just "cp -r" both repos before the "fetch --update-shallow" and that might do the trick.
On 3/24/2022 6:06 PM, Taylor Blau wrote: > This made me think of some of the difficulties we encountered back in > ce16364e89 (commit.c: don't persist substituted parents when > unshallowing, 2020-07-08), particularly: > > One way to fix this would be to reset the parsed object pool entirely > (flushing the cache and thus preventing subsequent reads from modifying > their parents) after unshallowing. That would produce a problem when > callers have a now-stale reference to the old pool, and so this patch > implements a different approach. > > if I can recall back to when that patch was written, I think the issue > was that dumping the entire set of parsed objects caused us to have > stale references in the commit-graph machinery. > > I'm not sure whether or not the same difficulties would be encountered > here, though. The shallow stuff is so tricky to me... The commit-graph is disabled in the presence of grafts, so this _should_ be fine. I guess there are some issues if you are transitioning not having grafts to having grafts (or vice-versa) so that might be worth investigating. Thanks, -Stolee
diff --git a/commit-reach.c b/commit-reach.c index c226ee3da4..7f4f3f7424 100644 --- a/commit-reach.c +++ b/commit-reach.c @@ -47,11 +47,15 @@ static int queue_has_nonstale(struct prio_queue *queue) return 0; } -/* all input commits in one and twos[] must have been parsed! */ +/* + * All input commits in twos[] must have been parsed. If + * one_is_at_min_generation is false, one must also have be parsed. + */ static struct commit_list *paint_down_to_common(struct repository *r, struct commit *one, int n, struct commit **twos, - timestamp_t min_generation) + timestamp_t min_generation, + int one_is_at_min_generation) { struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; struct commit_list *result = NULL; @@ -66,7 +70,8 @@ static struct commit_list *paint_down_to_common(struct repository *r, commit_list_append(one, &result); return result; } - prio_queue_put(&queue, one); + if (!one_is_at_min_generation) + prio_queue_put(&queue, one); for (i = 0; i < n; i++) { twos[i]->object.flags |= PARENT2; @@ -97,6 +102,10 @@ static struct commit_list *paint_down_to_common(struct repository *r, /* Mark parents of a found merge stale */ flags |= STALE; } + + if (commit == one && one_is_at_min_generation) + continue; + parents = commit->parents; while (parents) { struct commit *p = parents->item; @@ -138,7 +147,7 @@ static struct commit_list *merge_bases_many(struct repository *r, return NULL; } - list = paint_down_to_common(r, one, n, twos, 0); + list = paint_down_to_common(r, one, n, twos, 0, 0); while (list) { struct commit *commit = pop_commit(&list); @@ -187,8 +196,6 @@ static int remove_redundant_no_gen(struct repository *r, redundant = xcalloc(cnt, 1); ALLOC_ARRAY(filled_index, cnt - 1); - for (i = 0; i < cnt; i++) - repo_parse_commit(r, array[i]); for (i = 0; i < cnt; i++) { struct commit_list *common; timestamp_t min_generation = commit_graph_generation(array[i]); @@ -207,7 +214,7 @@ static int remove_redundant_no_gen(struct repository *r, min_generation = curr_generation; } common = paint_down_to_common(r, array[i], filled, - work, min_generation); + work, min_generation, 1); if (array[i]->object.flags & PARENT2) redundant[i] = 1; for (j = 0; j < filled; j++) @@ -478,8 +485,6 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit, int ret = 0, i; timestamp_t generation, max_generation = GENERATION_NUMBER_ZERO; - if (repo_parse_commit(r, commit)) - return ret; for (i = 0; i < nr_reference; i++) { if (repo_parse_commit(r, reference[i])) return ret; @@ -495,7 +500,7 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit, bases = paint_down_to_common(r, commit, nr_reference, reference, - generation); + generation, 1); if (commit->object.flags & PARENT2) ret = 1; clear_commit_marks(commit, all_flags); diff --git a/t/t5537-fetch-shallow.sh b/t/t5537-fetch-shallow.sh index 92948de7a0..f736ccf9f5 100755 --- a/t/t5537-fetch-shallow.sh +++ b/t/t5537-fetch-shallow.sh @@ -136,6 +136,8 @@ test_expect_success 'fetch that requires changes in .git/shallow is filtered' ' ' test_expect_success 'fetch --update-shallow' ' + git init a-submodule && + test_commit -C a-submodule foo && ( cd shallow && git checkout main && @@ -145,10 +147,13 @@ test_expect_success 'fetch --update-shallow' ' ) && ( cd notshallow && + git submodule add ../a-submodule a-submodule && + git commit -m "added submodule" && git fetch --update-shallow ../shallow/.git refs/heads/*:refs/remotes/shallow/* && git fsck && git for-each-ref --sort=refname --format="%(refname)" >actual.refs && cat <<-\EOF >expect.refs && + refs/heads/main refs/remotes/shallow/main refs/remotes/shallow/no-shallow refs/tags/heavy-tag @@ -162,8 +167,6 @@ test_expect_success 'fetch --update-shallow' ' ' test_expect_success 'fetch --update-shallow into a repo with submodules' ' - git init a-submodule && - test_commit -C a-submodule foo && git init repo-with-sub && git -C repo-with-sub submodule add ../a-submodule a-submodule && git -C repo-with-sub commit -m "added submodule" && @@ -185,6 +188,7 @@ test_expect_success 'fetch --update-shallow (with fetch.writeCommitGraph)' ' git fsck && git for-each-ref --sort=refname --format="%(refname)" >actual.refs && cat <<-EOF >expect.refs && + refs/heads/main refs/remotes/shallow/main refs/remotes/shallow/no-shallow refs/tags/heavy-tag
When a commit is parsed, it pretends to have a different (possibly empty) list of parents if there is graft information for that commit. But there is a bug that could occur when a commit is parsed, the graft information is updated (for example, when a shallow file is rewritten), and the same commit is subsequently used: the parents of the commit do not conform to the updated graft information, but the information at the time of parsing. This is usually not an issue, as a commit is usually introduced into the repository at the same time as its graft information. That means that when we try to parse that commit, we already have its graft information. However, this is not the case when fetching with --update-shallow. In post_assign_shallow() in shallow.c, a revision walk is done that also parses commits at the shallow boundary before updating the shallow information (and hence, the graft information). (This revision walk needs to be done before the update because the nature of the update depends on the outcome of the revision walk.) If we were to revision-walk such a commit (at the shallow boundary), we would end up trying and failing to parse its parents because its list of parents is not empty (since it was parsed before there was any graft information telling us to conceal its parents). This revision walk will happen if the client has submodules, as it will revision-walk the fetched commits to check for new submodules, triggering this bug. This revision walk in post_assign_shallow() actually does not need to go beyond the shallow boundaries, so the solution is twofold: (1) do not iterate beyond such commits, and (2) in doing so, we no longer need to parse them, so do not parse them. To do (1), do something similar to d7c1ec3efd ("commit: add short-circuit to paint_down_to_common()", 2018-05-22), which taught paint_down_to_common() the concept of "min_generation": commits older than that generation do not need to be iterated over. Introduce yet another parameter that indicates whether "one" is of that minimum generation. If yes, we never need to iterate over its ancestors, so we do not need to add it to the priority queue in the first place. And if we reach it (because another input commit has it as an ancestor), we do not need to add its parents to the priority queue. There are only a few callers, so update all of them (including the one that matters for this bug - repo_in_merge_bases_many()) to indicate whether we know that "one" is of the minimum generation. To do (2), just delete the code that parses it. This solves the problem, because the commit is now only parsed during the revision walk that checks for new submodules, which happens after the shallow information is written. Signed-off-by: Jonathan Tan <jonathantanmy@google.com> --- This is on jt/reset-grafts-when-resetting-shallow. I tried figuring out a better reproduction recipe, but couldn't (I couldn't figure out what the local repo should contain with respect to the remote repo in order to reproduce this bug without just modifying an existing test). If anyone has any suggestions, please let me know. --- commit-reach.c | 25 +++++++++++++++---------- t/t5537-fetch-shallow.sh | 8 ++++++-- 2 files changed, 21 insertions(+), 12 deletions(-)