Re: [PATCH 13/16] prune: keep objects reachable from recent objects

[Michael Haggerty <mhagger@alum.mit.edu>]

On 10/03/2014 10:39 PM, Jeff King wrote:
> [...]
> Instead, this patch pushes the extra work onto prune, which
> runs less frequently (and has to look at the whole object
> graph anyway). It creates a new category of objects: objects
> which are not recent, but which are reachable from a recent
> object. We do not prune these objects, just like the
> reachable and recent ones.
> 
> This lets us avoid the recursive check above, because if we
> have an object, even if it is unreachable, we should have
> its referent:
> 
>   - if we are creating new objects, then we cannot create
>     the parent object without having the child
> 
>   - and if we are pruning objects, will not prune the child
>     if we are keeping the parent
> 
> The big exception would be if one were to write the object
> in a way that avoided referential integrity (e.g., using
> hash-object). But if you are in the habit of doing that, you
> deserve what you get.
> 
> Naively, the simplest way to implement this would be to add
> all recent objects as tips to the reachability traversal.
> However, this does not perform well. In a recently-packed
> repository, all reachable objects will also be recent, and
> therefore we have to consider each object twice (both as a
> tip, and when we reach it in the traversal). I tested this,
> and it added about 10s to a 30s prune on linux.git. This
> patch instead performs the normal reachability traversal
> first, then follows up with a second traversal for recent
> objects, skipping any that have already been marked.

I haven't read all of the old code, but if I understand correctly this
is your new algorithm:

1. Walk from all references etc., marking reachable objects.

2. Iterate over *all* objects, in no particular order, skipping the
   objects that are already known to be reachable. Use any unreachable
   object that has a recent mtime as a tip for a second traversal that
   marks all of its references as "to-keep".

3. Iterate over any objects that are not marked "to-keep". (I assume
   that this iteration is in no particular order.) For each object:

   * [Presumably] verify that its mtime is still "old"
   * If so, prune the object

I see some problems with this.

* The one that you mentioned in your cover letter, namely that prune's
  final mtime check is not atomic with the object deletion. I agree
  that this race is so much shorter than the others that we can accept
  a solution that doesn't eliminate it, so let's forget about this one.

* If the final mtime check fails, then the object is recognized as new
  and not pruned. But does that prevent its referents from being pruned?

  * When this situation is encountered, you would have to start another
    object traversal starting at the "renewed" object to mark its
    referents "to-keep". I don't see that you do this. Another, much
    less attractive alternative would be to abort the prune operation
    if this situation arises. But even if you do one of these...

  * ...assuming the iteration in step 3 is in no defined order, a
    referent might *already* have been pruned before you notice the
    "renewed" object.

So although your changes are a big improvement, it seems to me that they
still leave a race with a window approximately as long as the time it
takes to scan and prune the unreachable objects.

I think that the only way to get rid of that race is to delete objects
in parent-to-child order; in other words, *only prune an object after
all objects that refer to it have been pruned*. This could be done by
maintaining reference counts of the to-be-pruned objects and only
deleting an object once its reference count is zero.


The next point that I'm confused by is what happens when a new object or
reference is created while prune is running, and the new object or
reference refers to old objects. I think when we discussed this
privately I claimed that the following freshenings would not be
necessary, but now I think that they are (sorry about that!).


Let's take the simpler case first. Suppose I run the following command
between steps 1 and 3:

    git update-ref refs/heads/newbranch $COMMIT

, where $COMMIT is a previously-unreachable object. This doesn't affect
the mtime of $COMMIT, does it? So how does prune know that it shouldn't
delete $COMMIT?

-> So ISTM that updating a reference (or any other traversal starting
point, like the index) must freshen the mtime of any object newly
referred to.


A more complicated case: suppose I create a new $COMMIT referring to an
old $TREE during step 2, *after* prune has scanned the directory that
now contains $COMMIT. (I.e., the scan in step 2 never notices $COMMIT.)
Then I create a new reference pointing at $COMMIT. (I.e., the scan in
step 1 never noticed that the reference exists.) None of this affects
the mtime of $TREE, does it? So how does prune know that it mustn't
prune $TREE?

-> It seems to me that the creation of $COMMIT has to freshen the mtime
of $TREE, so that the final mtime check in step 3 realizes that it
shouldn't prune $TREE. Or to generalize, whenever a new object is
created which refers to existing objects, the direct referents of the
new object have to have their mtimes freshened. However, when an attempt
to write a new object accidentally coincides with an object that already
exists, *that* object needs to be freshened but *its* referents do *not*.


I hope I understood that all correctly...

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu