From: Junio C Hamano <hidden> Date: 2021-11-11 17:32:34
Jeff King [off-list ref] writes:
On Tue, Nov 09, 2021 at 04:59:29PM -0800, Junio C Hamano wrote:
quoted
* The revision traversal API has been optimized by taking advantage
of the commit-graph, when available, to determine if a commit is
reachable from any of the existing refs.
I was thinking a bit about this change, specifically f45022dc2f
(connected: do not sort input revisions, 2021-08-09). At the time, Junio
said[1]:
Sorting of positive side is done to help both performance and
correctness in regular use of the traversal machinery, especially
when reachability bitmap is not in effect, but on the negative side
I do not think there is any downside to omit sorting offhand. The
only case that may get affected is when the revision.c::SLOP kicks
in to deal with oddball commits with incorrect committer timestamps,
but then the result of the sorting isn't to be trusted anyway, so...
But wouldn't failure to sort the commits actually _create_ such an
"oddball commits" scenario, because we'd see the UNINTERESTING commits
in an arbitrary order, especially with respect to the interesting ones?
You're right.
So indeed, we get confused by the unsorted input and give the wrong
answer. We should look at and propagate UNINTERESTING marks from day-9,
etc on down to day-1, but we don't.
Now in this case, we're sending too much output, which is OK for the
purposes of the connectivity check. It will just walk day-1 and its
tree unnecessarily, which is a performance loss but not incorrect.
The primary use of the traversal in check_connected() is when we
have new refs we haven't seen, and they go to the positive end of
the traversal, which will end in the refs we do have (there may be
tons). The idea is that when one or more of the new refs are truly
"new" in the sense that one or more the objects necessary to connect
them to our refs do not exist, not even in the "not reachable but
not yet pruned" state, this traversal will hit a missing object and
will error out. So, it is alarming that "day-1" is shown without
painted uninteresting via any of the negative [day-4..day-9]
commits. Which means, if we are checking if we need to initiate a
real fetch to connect day-1 and day-10 to our DAG, when we think we
have [day-4..day-9] and everything behind them, we stopped traversal
before seeing all the "objects necessary to connect them to our
refs". If day-2 were missing in our repository, we would have
noticed if we did traversal from sorted tips, but the unsorted
traversal happily misses it.
Not that noticing that day-2 is missing from our repository does not
help much in *this* particular case, though. It is likely that a
common negotiation would say "I have [day-4..day-9], and want day-1
and day-10", that is reponded with "OK, I know enough, here is
day-10 and its tree/blob that would be missing from a healthy clone
with everything behind day-9", and it won't include day-2 (nor
day-1). So in this particular example, it would not matter if the
new unsorted traversal is subtly broken (I think the extent of the
damage is similar to making the SLOP problem deliberately worse),
but I am not sure if there are other failure modes that would yield
outright incorrect result.
My intuition is that this is _probably_ the only type of incorrect
answer we'd give (i.e., that we'd never go the other way, omitting an
object we should have included) because nobody would ever set the
UNINTERESTING flag unnecessarily, and everybody_uninteresting() does do
a full scan looking for any positive tips.
Still, I didn't see this subtlety mentioned in the earlier discussion,
and it's a bit alarming not to understand all of the possible
implications. I'm not sure if it rises to the level of something we want
to consider more or address before the release. Sorry to only come up
with this at the -rc2 stage, but I figure now is better than right after
the release. ;)
-Peff
[1] https://lore.kernel.org/git/xmqqa6lzwu31.fsf@gitster.g/
We probably should revert this step as it can affect correctness in
a big way, but I wonder if the other steps in the same series, or
other topic that came later, rely on it.
At the very least, I think this may be prudent during -rc period,
but on the other hand, I do not know offhand what would later
pursuade us to reinstate it and convince us that it is a safe thing
to do.
connected.c | 1 -
1 file changed, 1 deletion(-)
From: Jeff King <hidden> Date: 2021-11-11 20:23:12
On Thu, Nov 11, 2021 at 09:32:29AM -0800, Junio C Hamano wrote:
quoted
Now in this case, we're sending too much output, which is OK for the
purposes of the connectivity check. It will just walk day-1 and its
tree unnecessarily, which is a performance loss but not incorrect.
The primary use of the traversal in check_connected() is when we
have new refs we haven't seen, and they go to the positive end of
the traversal, which will end in the refs we do have (there may be
tons). The idea is that when one or more of the new refs are truly
"new" in the sense that one or more the objects necessary to connect
them to our refs do not exist, not even in the "not reachable but
not yet pruned" state, this traversal will hit a missing object and
will error out. So, it is alarming that "day-1" is shown without
painted uninteresting via any of the negative [day-4..day-9]
commits. Which means, if we are checking if we need to initiate a
real fetch to connect day-1 and day-10 to our DAG, when we think we
have [day-4..day-9] and everything behind them, we stopped traversal
before seeing all the "objects necessary to connect them to our
refs". If day-2 were missing in our repository, we would have
noticed if we did traversal from sorted tips, but the unsorted
traversal happily misses it.
Yes, but if day-2 were missing in our repository, then we are already
corrupt. And in most cases we would not notice adding a new ref that is
also corrupt (e.g., imagine adding _just_ day-10 which is a descendent
of day-2, but we stop traversal at day-9 when we see that we already
have it reachable).
So I don't think it is actually changing the check_connected() outcome.
I couldn't come up with a case where we should be checking a commit and
don't. Only the other way around.
Not that noticing that day-2 is missing from our repository does not
help much in *this* particular case, though. It is likely that a
common negotiation would say "I have [day-4..day-9], and want day-1
and day-10", that is reponded with "OK, I know enough, here is
day-10 and its tree/blob that would be missing from a healthy clone
with everything behind day-9", and it won't include day-2 (nor
day-1). So in this particular example, it would not matter if the
new unsorted traversal is subtly broken (I think the extent of the
damage is similar to making the SLOP problem deliberately worse),
but I am not sure if there are other failure modes that would yield
outright incorrect result.
Yes, I think that framing is right: it is making SLOP much worse. We
could similarly have had bogus timestamps in those commits which would
cause the same outcome. So in that sense it is nothing new. On the other
hand, I wonder how often it will cause extra traversal work (keeping in
mind that this commit traversal is just the first stage; after we find
the commits, then we talk all of their trees, which is the more
expensive part).
For the case of adding new commits directly on top of another branch, I
think there would be no change. But any time you have to walk down to a
common fork point (e.g., imagine I made a new branch forked from an old
bit of history), we may fail to find that. I haven't quite constructed
an example, but I have a feeling we could end up walking over
arbitrarily long segments of history.
We probably should revert this step as it can affect correctness in
a big way, but I wonder if the other steps in the same series, or
other topic that came later, rely on it.
I looked them over, and I think this is pretty independent (with the
exception of the refactoring of the no_walk/unsorted flags, but
obviously that had to come first).
quoted hunk
At the very least, I think this may be prudent during -rc period,
but on the other hand, I do not know offhand what would later
pursuade us to reinstate it and convince us that it is a safe thing
to do.
[...]
@@ -107,7 +107,6 @@ int check_connected(oid_iterate_fn fn, void *cb_data,if(opt->progress)strvec_pushf(&rev_list.args,"--progress=%s",_("Checking connectivity"));-strvec_push(&rev_list.args,"--unsorted-input");rev_list.git_cmd=1;rev_list.env=opt->env;
This seems like a pretty safe and minimal backing-out for the -rc
period. We would still ship with "--unsorted-input" as an option (and
mentioned in the docs), though. If we're worried that it might be a dead
end and we don't want to support it, we could revert f45022dc2f
(connected: do not sort input revisions, 2021-08-09) entirely. That
carries a little more risk of accidentally breaking something during the
revert, but from my reading of the patch it should be pretty safe.
I'd be curious to hear Patrick's thoughts on the whole thing.
-Peff
From: Patrick Steinhardt <hidden> Date: 2021-11-15 15:07:25
On Thu, Nov 11, 2021 at 03:23:08PM -0500, Jeff King wrote:
On Thu, Nov 11, 2021 at 09:32:29AM -0800, Junio C Hamano wrote:
quoted
quoted
Now in this case, we're sending too much output, which is OK for the
purposes of the connectivity check. It will just walk day-1 and its
tree unnecessarily, which is a performance loss but not incorrect.
The primary use of the traversal in check_connected() is when we
have new refs we haven't seen, and they go to the positive end of
the traversal, which will end in the refs we do have (there may be
tons). The idea is that when one or more of the new refs are truly
"new" in the sense that one or more the objects necessary to connect
them to our refs do not exist, not even in the "not reachable but
not yet pruned" state, this traversal will hit a missing object and
will error out. So, it is alarming that "day-1" is shown without
painted uninteresting via any of the negative [day-4..day-9]
commits. Which means, if we are checking if we need to initiate a
real fetch to connect day-1 and day-10 to our DAG, when we think we
have [day-4..day-9] and everything behind them, we stopped traversal
before seeing all the "objects necessary to connect them to our
refs". If day-2 were missing in our repository, we would have
noticed if we did traversal from sorted tips, but the unsorted
traversal happily misses it.
Yes, but if day-2 were missing in our repository, then we are already
corrupt. And in most cases we would not notice adding a new ref that is
also corrupt (e.g., imagine adding _just_ day-10 which is a descendent
of day-2, but we stop traversal at day-9 when we see that we already
have it reachable).
So I don't think it is actually changing the check_connected() outcome.
I couldn't come up with a case where we should be checking a commit and
don't. Only the other way around.
quoted
Not that noticing that day-2 is missing from our repository does not
help much in *this* particular case, though. It is likely that a
common negotiation would say "I have [day-4..day-9], and want day-1
and day-10", that is reponded with "OK, I know enough, here is
day-10 and its tree/blob that would be missing from a healthy clone
with everything behind day-9", and it won't include day-2 (nor
day-1). So in this particular example, it would not matter if the
new unsorted traversal is subtly broken (I think the extent of the
damage is similar to making the SLOP problem deliberately worse),
but I am not sure if there are other failure modes that would yield
outright incorrect result.
Yes, I think that framing is right: it is making SLOP much worse. We
could similarly have had bogus timestamps in those commits which would
cause the same outcome. So in that sense it is nothing new. On the other
hand, I wonder how often it will cause extra traversal work (keeping in
mind that this commit traversal is just the first stage; after we find
the commits, then we talk all of their trees, which is the more
expensive part).
For the case of adding new commits directly on top of another branch, I
think there would be no change. But any time you have to walk down to a
common fork point (e.g., imagine I made a new branch forked from an old
bit of history), we may fail to find that. I haven't quite constructed
an example, but I have a feeling we could end up walking over
arbitrarily long segments of history.
Sorry, but I'm currently completely loaded with work and thus didn't
find the capacity to have a deeper look yet and will probably not find
the time for a few more days. So the earliest I can have a look at this
is probably beginning next week.
With that in mind, I'm happy to have this change reverted for now, as it
is...
quoted
We probably should revert this step as it can affect correctness in
a big way, but I wonder if the other steps in the same series, or
other topic that came later, rely on it.
I looked them over, and I think this is pretty independent (with the
exception of the refactoring of the no_walk/unsorted flags, but
obviously that had to come first).
.. completely independent of the other patches in this series and can be
reverted on its own. Only question is whether we also want to revert the
patch introducing this option in the first place given that it would end
up without a user afterwards.
Patrick
quoted
At the very least, I think this may be prudent during -rc period,
but on the other hand, I do not know offhand what would later
pursuade us to reinstate it and convince us that it is a safe thing
to do.
[...]
@@ -107,7 +107,6 @@ int check_connected(oid_iterate_fn fn, void *cb_data,if(opt->progress)strvec_pushf(&rev_list.args,"--progress=%s",_("Checking connectivity"));-strvec_push(&rev_list.args,"--unsorted-input");rev_list.git_cmd=1;rev_list.env=opt->env;
This seems like a pretty safe and minimal backing-out for the -rc
period. We would still ship with "--unsorted-input" as an option (and
mentioned in the docs), though. If we're worried that it might be a dead
end and we don't want to support it, we could revert f45022dc2f
(connected: do not sort input revisions, 2021-08-09) entirely. That
carries a little more risk of accidentally breaking something during the
revert, but from my reading of the patch it should be pretty safe.
I'd be curious to hear Patrick's thoughts on the whole thing.
-Peff
From: Jeff King <hidden> Date: 2021-11-15 15:27:51
On Mon, Nov 15, 2021 at 04:06:45PM +0100, Patrick Steinhardt wrote:
Sorry, but I'm currently completely loaded with work and thus didn't
find the capacity to have a deeper look yet and will probably not find
the time for a few more days. So the earliest I can have a look at this
is probably beginning next week.
With that in mind, I'm happy to have this change reverted for now, as it
is...
Thanks for chiming in (and again, sorry for bringing this up so late in
the cycle).
quoted
quoted
We probably should revert this step as it can affect correctness in
a big way, but I wonder if the other steps in the same series, or
other topic that came later, rely on it.
I looked them over, and I think this is pretty independent (with the
exception of the refactoring of the no_walk/unsorted flags, but
obviously that had to come first).
.. completely independent of the other patches in this series and can be
reverted on its own. Only question is whether we also want to revert the
patch introducing this option in the first place given that it would end
up without a user afterwards.
It looks like Junio queued a revert of the whole patch in a7df4f52af
(Revert "connected: do not sort input revisions", 2021-11-11), which is
on "master". So I think we should have a clean slate to look at this in
the next cycle.
-Peff
From: Jeff King <hidden> Date: 2021-11-15 16:52:58
On Thu, Nov 11, 2021 at 03:23:09PM -0500, Jeff King wrote:
Yes, I think that framing is right: it is making SLOP much worse. We
could similarly have had bogus timestamps in those commits which would
cause the same outcome. So in that sense it is nothing new. On the other
hand, I wonder how often it will cause extra traversal work (keeping in
mind that this commit traversal is just the first stage; after we find
the commits, then we talk all of their trees, which is the more
expensive part).
For the case of adding new commits directly on top of another branch, I
think there would be no change. But any time you have to walk down to a
common fork point (e.g., imagine I made a new branch forked from an old
bit of history), we may fail to find that. I haven't quite constructed
an example, but I have a feeling we could end up walking over
arbitrarily long segments of history.
I was playing around with this a bit more, and there is one subtlety in
the "day-10" snippet I showed that I hadn't noted before. It's important
the day-1 does not have any parents. If we used day-2 instead, then
limit_list() would insert its parent (day-1, in this case) into the
queue, without an UNINTERESTING flag (because it's the parent of
something interesting). And thus when we call still_interesting(), we
would never decrement the slop counter, because we know we are still
walking back to something potentially interesting.
This "works" because we put the new commit at the end of the list via
commit_list_insert_by_date(). That can be fooled, of course, because
it's assuming the list is already in sorted order (which it isn't). So
there could be an "old" commit at the front, and we place the parent in
front of that, even though it's UNINTERESTING descendants are further
back in the list.
So I do think we could walk an arbitrary string of history in this way,
all the way down to the root, or to something else pointed to by a ref
tip. Here's the example I came up with:
-- >8 --
git init -q repo
cd repo
commit_at() {
echo $1 >$1
git add .
base=1234567890
unit=86400
timestamp="@$((base + $1 * unit)) +0000"
GIT_COMMITTER_DATE=$timestamp \
GIT_AUTHOR_DATE=$timestamp \
git commit -qm "commit at day $1"
}
# imagine a bunch of base history
for i in $(seq 100); do
commit_at $i
done
git tag base
# And then we have some older branches hanging around.
for i in $(seq 1 10); do
git checkout -b branch-$i base~$((60+$i))
done
# But also a newer one; it's important that this refname
# sort after the other ones, because that's what confuses
# the sorting.
git branch new-branch
# and then somebody pushes/fetches a branch based on an old part of history,
# newer than our old branches, but older than our new one.
#
# We won't actually create the branch here, because we're simulating the state
# before the ref is created, when we do the connectivity check.
old_commit=$(git rev-parse base~50)
new_commit=$(echo foo | git commit-tree -p $old_commit HEAD^{tree})
# and now here's the connectivity check we would do
git rev-list $new_commit --not --all >expect
git rev-list --unsorted-input $new_commit --not --all >actual
diff -u expect actual
-- >8 --
That will report all of base~60..base~50 in the output, when it should
just report the single new commit.
I don't think any of this changes the plan for the 2.34 release (in
fact, it makes me more confident that reverting this change was the
right thing to do). I'm just recording my notes here for revisiting the
topic later.
My suspicion is that there's no easy way to make this work. We're
violating the assumption in still_interesting() that it can easily find
the lowest-date commit. We could drop that assumption for the unsorted
case, but then I think we'd be forced to walk all the way to the root
commits, which is even worse than sorting the tips.
I suspect a better solution would be to make use of generation numbers
from the commit graph if we have them. The --topo-order stuff already
does this, and I kind of wonder if we could piggy-back on that.
-Peff