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

On 10/03/2014 10:39 PM, Jeff King wrote:

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