• Jeff King's avatar
    prune: keep objects reachable from recent objects · d3038d22
    Jeff King authored
    Our current strategy with prune is that an object falls into
    one of three categories:
      1. Reachable (from ref tips, reflogs, index, etc).
      2. Not reachable, but recent (based on the --expire time).
      3. Not reachable and not recent.
    We keep objects from (1) and (2), but prune objects in (3).
    The point of (2) is that these objects may be part of an
    in-progress operation that has not yet updated any refs.
    However, it is not always the case that objects for an
    in-progress operation will have a recent mtime. For example,
    the object database may have an old copy of a blob (from an
    abandoned operation, a branch that was deleted, etc). If we
    create a new tree that points to it, a simultaneous prune
    will leave our tree, but delete the blob. Referencing that
    tree with a commit will then work (we check that the tree is
    in the object database, but not that all of its referred
    objects are), as will mentioning the commit in a ref. But
    the resulting repo is corrupt; we are missing the blob
    reachable from a ref.
    One way to solve this is to be more thorough when
    referencing a sha1: make sure that not only do we have that
    sha1, but that we have objects it refers to, and so forth
    recursively. The problem is that this is very expensive.
    Creating a parent link would require traversing the entire
    object graph!
    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. We can make a simple inductive argument that
    with this patch, this property holds (that there are no
    objects with missing referents in the repository):
      0. When we have no objects, we have nothing to refer or be
         referred to, so the property holds.
      1. If we add objects to the repository, their direct
         referents must generally exist (e.g., if you create a
         tree, the blobs it references must exist; if you create
         a commit to point at the tree, the tree must exist).
         This is already the case before this patch. And it is
         not 100% foolproof (you can make bogus objects using
         `git hash-object`, for example), but it should be the
         case for normal usage.
         Therefore for any sequence of object additions, the
         property will continue to hold.
      2. If we remove objects from the repository, then we will
         not remove a child object (like a blob) if an object
         that refers to it is being kept. That is the part
         implemented by this patch.
         Note, however, that our reachability check and the
         actual pruning are not atomic. So it _is_ still
         possible to violate the property (e.g., an object
         becomes referenced just as we are deleting it). This
         patch is shooting for eliminating problems where the
         mtimes of dependent objects differ by hours or days,
         and one is dropped without the other. It does nothing
         to help with short races.
    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 look at each object twice. This patch
    instead performs the reachability traversal, then follows up
    with a second traversal for recent objects, skipping any
    that have already been marked.
    Signed-off-by: default avatarJeff King <peff@peff.net>
    Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
reachable.c 5.87 KB