gc.sh: the new order

gc.sh: the new order

In the very beginning Girocco used repack -A -d when running
garbage collection.  That quickly became -a -d instead.
Eventually though that migrated back to -A -d.

The flip-flops represent a switch between wanting to be as efficient
as possible and avoid having loose objects lying around if at all
possible and the need to keep objects that have recently become
unreachable or are in the process of becoming reachable around long
enough for them to become reachable (via a ref change) or no longer
be needed (for a ref notification message).

On the one hand the "-a -d" options give efficiency but risk
repository corruption due to Git race conditions with siumltaneous
pushes and garbage collection.  On the other hand the "-A -d"
options can produce extensive loose object splatter resulting in
lost efficiency and disk space.  With "-A -d" the "git prune"
command must be used and that has its own race conditions.

By using a number of extra helpers in the hooks and configuration
options, Girocco has gotten along with a "git repack -A -d" + "git
prune --expire=1.day.ago" + hard-linking loose objects into child
forks technique that eliminates most of the race conditions (the
"Push Pack Redux" described in README-GC was not handled) and makes
simultaneous pushing and garbage collection safe at the expense of
some serious loose object splatter when commits are discared (either
via non-fast-forward updates or outright ref deletion).

The current situation remains unsatisfactory from an efficiency
standpoint.

Now we revamp the way Girocco does garbage collection and eliminate
use of both the -A and -d options.  In fact, we eliminate use of
git repack and git prune entirely in order to remedy the situation.

To get a finer amount of control over what happens and when, we
switch to using git pack-objects directly.  With the exception of
the "--write-bitmap-index" option, all the options we might want
to pass to pack-objects have been available since before Git v1.6.6
which is now the minimum Girocco requires.  That makes it not really
all that complex to use pack-objects directly.

The new garbage collection strategy itself is not quite so simple.

We adopt a new four phase garbage collection strategy:

  I) Create a new all-in-one pack (this pack may have a bitmap)
 II) Create a pack of "recently reachable" objects and "friends"
III) Create a pack of "unreachable" objects if any child forks exist
 IV) Migrate all remaining loose objects into a pack

Phase I corresponds basically to "git repack -a".  Note that there's
no deletion or removal going on during phase I.  Non-forks will get
a bitmap (with Git v2.1.0 or later) and this pack will serve as the
"virtual bundle".

Phase II became possible when Girocco started keeping a record of
ref changes in the reflogs subdirectory (the pre-receive hook and
the update.sh script are responsible for this).  We simply do another
full packing after adding temporary refs for everything in the
reflogs directory (that's not too old) and, in a nod to linked
working trees, ref logs, index files and detached HEADs are included
as "friends".  By manipulating the packing options it's easy to
exclude everything that was already packed in phase I.

Phase III will be skipped unless forks are present.  One more
iteration over the same set of refs Phase II used but passing the
"--keep-unreachable" option and excluding everything packed in
either phase I or phase II (or in phase III packs hard-linked into
the fork from its parent) gives us this pack.  It won't appear in
the project itself, but will be hard-linked to all immediate child
forks which will in turn hard-link it down to their children, if
any, when they run gc.

At this point any non-keep packs that existed prior to phase I can
be removed (this includes phase III packs that had been hard-linked
down from the parent).  Special techniques are used to avoid a "Push
Pack Redux" race and to not remove any packs that have been "freshened"
by some kind of simultaneous non-Girocco loose object activity.

Phase IV can be accomplished simply by packing all loose objects
that are not already in a phase I or phase II pack.  We deliberately
exclude any phase III packs here in an attempt to make sure that
any unreachable loose objects live on for at least one min_gc_interval.
This again is a nod to possible linked working trees.  A final "git
prune-packed" takes care of removing loose object detritus.

At first blush this may appear to be more work.  It is.  But only
very slightly.  Previously the "git repack -A -d" was doing a full
reachability trace and so was the following "git prune".  The "git
prune-packed" operation (which is very fast, slow file systems
notwithstanding), was being done internally by the "git repack"
command.  In effect there's only one additional reachability trace
that was not being done before and then only if any forks are
present.  It has the benefit of having a nice new all-in-one pack
to work with that has just recently been in the disk cache.  There
is the savings from not having to deal with loose object splatter,
but unless the file system really under performs that will probably
not quite offset the time for the extra reachability trace in phase
III.  Also it will not actually pack anything unless there have
been any discarded commits.

For that matter, phase II also will not pack anything unless there
have been discarded commits.  Phase IV will not produce any pack
unless some non-Girocco activity has produced loose objects (Girocco
takes care to make sure its external VCS imports pack up their
leftings).  Also phase IV does NOT do a reachability trace, it only
looks in the loose object directories.  In the absence of loose
objects it takes practically no time at all.

This means that in the absense of discarded commits there will still
be only one pack remaining after gc runs.  (Unless the pack.packSizeLimit
config option has been set and it caused multiple packs to be
produced which is tolerated but not recommended.)

The only thing that will be hard-linked down to child forks are the
phase III packs (and then only if they're non-empty).

This represents a huge improvement over hard-linking all the loose
object splatter created by "git repack -A -d".

As part of this "new order," non-Girocco operations on the repository
(such as use of linked working trees) are "tolerated."

Since Git has no such thing as a "looseobject.keep" file, there
will always be a race possible between new objects becoming reachable
(via a ref update) and garbage collection having decided they're
unreachable and removing them.  The window remains very small.
Miniscule in fact.  But it does exist.  There is no such problem
with simulataneous incoming pushes and garbage collection (with the
new order even the "Push Pack Redux" hole has been closed).

If that "miniscule" window of opportunity for repository corruption
cannot be accepted, linked working trees (or even using Girocco on
non-bare repositories -- oh, the horror) must not be used and all
new content needs to be "pushed" into the repository from a clone
(one that does _not_ make use of the --reference facility either)
or else the timing of gc operations must be strictly controlled to
guarantee that no preexisting unreachable objects are becoming
reachable during gc.

We also take this opportunity to update the README-GC documentation
and modify the perform-pre-gc-linking.sh script to reflect the new
order of things.

Signed-off-by: Kyle J. McKay <mackyle@gmail.com>