diff mbox series

commit-reach: do not parse and iterate minima

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

Commit Message

Jonathan Tan March 23, 2022, 9:08 p.m. UTC
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(-)

Comments

Junio C Hamano March 23, 2022, 11:30 p.m. UTC | #1
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?
Bagas Sanjaya March 24, 2022, 12:05 p.m. UTC | #2
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?
Derrick Stolee March 24, 2022, 3:27 p.m. UTC | #3
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
Derrick Stolee March 24, 2022, 3:29 p.m. UTC | #4
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
Taylor Blau March 24, 2022, 10:06 p.m. UTC | #5
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
Jonathan Tan March 24, 2022, 10:15 p.m. UTC | #6
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.
Jonathan Tan March 24, 2022, 10:19 p.m. UTC | #7
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.
Jonathan Tan March 24, 2022, 10:21 p.m. UTC | #8
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.
Derrick Stolee March 25, 2022, 2:32 p.m. UTC | #9
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 mbox series

Patch

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