cvmfs/cvmfs — pull request #605 by reneme (2014-11-20 14:21:09+00:00)
Title: Feature: Garbage Collection

This is the first incarnation of a garbage collection feature. It makes heavy use of the `CatalogTraversal` class to crawl through the whole catalog graph of a repository and sweeps unneeded data objects. To find these objects, it uses a (currently pretty naïve) implementation of mark-and-sweep.

Internally the `GarbageCollector` class uses a `HashFilter`, that is filled with objects found in catalogs that need to be preserved. After this initialisation phase, `GarbageCollector` traverses all condemned catalogs and checks each of their hashes against the pre-initialised `HashFilter`. If the object is not referenced there, it is garbage and can be thrown away.

The implementation of the `HashFilter` is currently a simple `std::set` and perhaps doesn't scale infinitely. Therefore the `GarbageCollector` class implements a strategy pattern with pluggable `HashFilters`. Usage of this possibility is left for future work.

The `GarbageCollector` itself is configurable like:

* Keep revisions up to a certain history depth
* Keep all revisions referenced by named snapshots
* Be verbose (list deleted objects)
* Dry Run: doesn't delete anything

Furthermore there is a unit test set checking the functionality of both the `GarbageCollector` and the `HashFilter`.