Subject: Re: [ANNOUNCE] Git v2.34.0-rc2

From: Patrick Steinhardt <[email-masked]>
Date: Mon, 15 Nov 2021 16:06:45 +0100

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:
> 
> > > 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.

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...

> > 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

> > 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.
> > [...]
> > diff --git c/connected.c w/connected.c
> > index cf68e37a97..35bd4a2638 100644
> > --- c/connected.c
> > +++ w/connected.c
> > @@ -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