Rework hash implementations to provide additional algorithms.

Provide a generic hash interface, rework SHA-1 to use the interface, and
also add code for SHA-224/SHA-256.

Add sha224/sha256 as supported hash algorithms.

Document new hash algorithms in the format description, and include all
supported algorithms in the Python code.  The cumulus binary does not yet
support the new algorithms.

Create a third_party directory for files copied from other projects.

Collected bugfixes, improvements, and cleanups.

 - Do not leak file descriptors when merging new include/exclude rules.
 - Improved error message when unable to open a directory.
 - Delete obsolete clean-segments.pl script (long since replaced by
   functionality in cumulus-util).

Update usage text for new include/exclude filtering mechanism.

First step towards a new, improved cumulus front-end.

This commit adds several things:
  - Rules for selecting sets of backups for expiration, for managing old
    snapshots.
  - A configuration file format and parser for listing settings such as
    backup expiration policies.
  - Code in a small utility library that can expire old snapshots
    according to configuration settings.

Eventually this code should be part of a new cumulus front-end in Python
that can integrate snapshot and database management with backup runs.

Refactor cumulus-util into a library plus small command front-end.

There is still more cleanup work to be done here, but this first step
makes commands in cumulus-util importable as a Python module for re-use
elsewhere.

Switch to hashlib (Python >= 2.5) for hash algorithms.

The old sha module is deprecated, and hashlib gives access to newer hash
algorithms.  Use it to add SHA-256 support as well.

Reimplement the file include/exclude filtering mechanism.

Implement something more similar to that rsync does.  Accept some number of
starting points for the backup, and an ordered set of include/exclude
patterns.  Also permit rules to be merged in during the backup process, by
per-subtree rule files.

Add a cache around getpwuid/getgrgid to avoid repeated calls.

Put linker flags at end of compiler command-line.

Put $(LDFLAGS) after the sources, since otherwise the linker may be unable
to find all symbols.

Update to support new snapshot version in Python tools.

Also, remove some older references to "lbs".

Some updates to the backup format:

  - The name of the descriptor file is now based on the timestamp in UTC,
    not local time.  This should give better behavior in the case of
    frequent snapshots and daylight saving time changes.
  - Update the backup format to v0.11 (other changes may yet come before
    release); with this also include a name change from "LBS" to "Cumulus"
    in the format name.

Rename scandir.cc to main.cc.

Prepare 0.10 release.

Enable additional compiler warnings

Apply fixes to s3:// URL parsing under Python 2.6.

The urlparse module starting in Python 2.6 appears to be compliant with RFC
3986, while previous versions were not.  This causes a change in the
behaviro of parsing s3:// URLs, however, resulting in breakage with Python
2.6.

Try to fix this by adjusting our code so that it works with either the old
or the new behavior.

add some further documentation on the sftp backend

* document that password auth and passowrd protected keys are not supported
* document the configuration via ~/.ssh/config
* document that the host key already has to be in ~/.ssh/known_hosts

fix usage of wrong variable

* fix some leftover reference to the wrong variable (self.path instead
  of self.netloc)

Formatting/spelling fix.

Some assorted fixes for the SFTP backend.

  - Automatically call the close() method of a storage backend when the
    object is garbage collected.
  - Calling stat in the SFTP backend when the file doesn't exist will raise
    a Cumulus NotFoundError instead of a generic IOError.
  - Avoid the use of keyword arguments when calling SFTPClient methods (in
    my testing the first argument might be called 'path' instead of
    'filename', but avoid the problem altogether by just using positional
    arguments).

code cleanup & regression fix

work for python 2.5

* import "with" statement from __future__ to be able to use it in 2.5

* document requirements for sftp storage

implement a basic sftp storage backend

* add an option to cumulus-store storage backends to explictly close the
  connection, needed because of the design of the ssh/sftp lib
* add a sftp storage backend based on paramiko

Have FTP backend reconnect on timeout.

Additionally, ensure that transfers are done in binary mode.

Patch provided by Ralf Schlatterbeck <rsc@runtux.com>.

The map::at method does not always exist, so instead use map::find.

Thanks to Achim J. Latz <achim.latz@qustodium.net>.

Ensure printf format specifiers and types match (fixes compiler warning).

Implement FTP backend and other code cleanups.

Details:

- Fix a race condition in setup of RemoteStore: The backup_script was
  set *after* a thread was already started. Sometimes this lead to a
  segfault because the thread tested the backup script twice. During the
  first test the variable wasn't yet defined while in the second test it
  was -- this lead to a segfault due to an uninitialized output file.
  I've move the backup_script to the constructor as an optional
  parameter.
cumulus-util:
- put all command-documentation into docstrings of respective function
- add the docstrings to the usage text, so that we know which commands
  exist
- Fix hard-coded extension '.tar.gpg' for cmd_list_snapshot_sizes
- framework for automatically computing the right method to call for a
  given command
python/cumulus/store/file.py:
- fix constructor so that we can directly call it when it's not called
  via the factory with an URL as parameter
- for NotFoundError give type and filename
python/cumulus/store/ftp.py:
- new FTP backend

Add a few items to the TODO list.

Fix a segfault-causing bug when converting a numeric group to a name fails.

The original code had a copy-and-paste bug when converting a numeric group
id into a symbolic group name: rather than checking that getgrgid returned
a valid result, it checked the result of getpwuid.  If any files in the
backup snapshot belonged to a non-existent group, this resulted in a
segfault.

Problem found and patch provided by Chris Wilson <chris@aptivate.org>.

Add --exclude-name option.

The --exclude-name will exclude from a snapshot files or directories with
the specified name.  This contrasts with --exclude, which requires that the
full path be specified.

Initial patch by Chris Wilson <chris@aptivate.org>.  Committed with minor
modifications.

Update for 0.9 release.

Update README with information about remote storage.

Include a missing header file.

This should fix compilation with newer versions of GCC.  Problem originally
reported by Robert Rebstock <rebstock@scienceworks.com>.

Implement rudimentary garbage collection.

Implement a garbage collection method in cumulus-util which will search for
files not referenced by any current snapshots and delete them.  This still
doesn't let snapshots themselves be deleted automatically, but after
manually deleting a snapshot this will quickly delete all other old files.

Implement metadata caching for S3 backend.

Amazon S3 will return some limited object metadata when a list operation is
performed.  This is significantly cheaper than fetching the information for
objects one at a time.  In the S3 backend, implement a scan() method that
will list all objects and cache the metadata, then return cached results
when stat() is called.

lbs-filter-gpg has been renamed to cumulus-filter-gpg.

An instance of this was missed in the code.  Caught by Achim J. Latz
<achim.latz@qustodium.net>.

Include segment add/remove counts in list-snapshot-sizes.

Detect decompression script needed for segments based on extension.

cumulus-sync: Create a tool for copying snapshots between locations.

This will automatically find and copy all needed segments that are not
already present, and can handle both local filesystems and remote storage
with Amazon S3.

Drop the use of exceptions for fatal error handling.

Improve handling of file-not-found in remote storage layer.

Implement a single NotFoundError which is thrown whenever a file does not
exist in any remote store, instead instance-specific error handling.

Delete contrib/cumulus-store-s3.

This has been replaced by cumulus-store, and the main cumulus executable
now uses a different interface so cumulus-store-s3 won't work any longer.

Re-do cumulus side of upload script interface.

Update the cumulus executable so that the interface for the remote upload
script is compatible with the new cumulus-store script, allowing cumulus to
easily target different storage backends.

Introduce a script to provide access to remote repositories.

cumulus-store is a Python script that uses the cumulus library code to
access various storage repositories (local file, S3, and extensible to
others).  It allows non-Python code to access these storage repositories
through a simple interface through stdin/stdout.

Additionally, make a few extensions and fixes to the cumulus Python
libraries.

Makefile: Fix clean target.

cumulus-util: Automatically set Python search path.

Attempt to set the Python library search path so that cumulus-util can find
the cumulus Python modules, without PYTHON_PATH having to be set
explicitly.

Modules are looked for in the "python" directory where the cumulus-util
binary resides; this is appropriate for running cumulus-util directly from
the source code directory, but may not be if the tools are installed
somewhere else.

cumulus-util: In list-snapshot-sizes output, display backup intent values.

Extend FUSE functionality.

Add caching of metadata for performance, and reading of file data.

Start a proof-of-concept FUSE interface to old snapshots.

Begin work on a FUSE interface to cumulus, allowing old snapshots to
displayed as a mounted filesystem.  Though only partly-implemented, already
it is possible to read the directory structure and stat information for
files.  File contents cannot yet be extracted.

To implement this efficiently, random access to cumulus metadata was
implemented through the use of a binary search.  Some optimization is still
needed, and some caching should probably still be added.

Allow a URL to be used in cumulus-util to specify a store location.

Both file:/// and s3:// URLs are supported, reading data from the local
filesystem or Amazon S3, respectively.  Local paths (without a file:///
prefix) can still be specified.

Begin new storage-abstraction layer.

Begin work on new Python code for providing uniform access to both local
filesystem and remote S3 storage.  Convert the existing Python module to
use the new interface.

Makefile cleanup.

Prepare for 0.8 release.

Fix typo in restore.pl.

Update restore.pl for new snapshot format (v0.8).

Rebuild sub-block signatures when --rebuild-statcache is specified.

Documentation updates.

Update help text to include --rebuild-statcache.

--rebuild-statcache bugfix.

Check that a file is actually unchanged (and not just present in the old
statcache with different metadata) before printing a warning about
differing checksums.

Add the --rebuild-statcache option.

Add an option which forces cumulus to re-read all files, even if they seem
not to have changed.

This has two main purposes: first, it helps to rebuild the contents of the
statcache from data actually on disk, and as such is useful for adding
object size annotations to files which haven't changed (ordinarily, the
straight re-use of data from the statcache prevents this).

Second, it can be used to detect some simple forms of data corruption; if a
file has not changed (according to stat information) but the checksum
doesn't match the old value in the statcache file, a warning is printed.

Better cope with null values in the segments_used table.

Treat nulls utilization values as 0.0 for cleaning purposes.  These
shouldn't come up, but may have been generated due to bugs in the SQLite
library, so deal gracefully with them instead of failing with an exception.

Make use of size assertions in references where possible.

When writing out a reference to what is known to be a complete object, use
the size-assertion form of a reference.

Eliminate a gcc warning.

Add parentheses around arithmetic near a shift operator, to get rid of a
gcc warning.  The code was correct before, and this change causes it to
diverge from the LBFS sources it was derived from, but it is worthwhile to
get rid of the gcc warning.

Extend object reference syntax with size assertions.

Object references can now include a size assertion, such as [=1024]
which indicates that the referenced object is exactly 1024 bytes in
length.  If a metadata log or statcache file is produced using this
reference form where appropriate, then it should be possible to rebuild
much of the object index in the local database (by looking for files
which are unchanged and computing hashes of blocks from that file where
it is known that an entire object was used, not just a fragment of an
object).

This commit merely adds support for parsing the new references; they are
not yet generated by any code.

Add some missing #include statements.

Some standard include files (stdlib.h and string.h) were not being included
where necessary.  This worked in the past, but seems to break for some
versions of the compiler/standard library, so be sure to include what we
need.

README corrections.

Document the "-v/--verbose" option.

NEWS updates for v0.7 release.

Add a verbose option to cumulus.

By default, do not output a listing of all files as they are backed up.  If
--verbose or -v is specified, then do so.

README updates: explain restores in more detail.

Compute checksum of checksums file while it still exists.

When data is being stored remotely, the checksums file (containing hashes
for all the segments needed by a snapshot) may only be stored locally for a
short period of time.  We can't wait to compute its checksum (for inclusion
into the root descriptor) until the time when the root descriptor is
writtenout, since the checksum file may be gone by then.

Compute the checksum earlier (before sending the checksums file to remote
storage), and save the checksum value until it is written out later.

Fix an example command in the README.

Updates to documentation and contributed scripts for name change.

Do not store subfile signatures for very short blocks.

Don't bother to store subfile signatures for very short files, since it is
probably not worth the effort: we're probably best off just storing a new
copy of the data if it changes anyway.

For now, we used a fixed and non-scientific threshold of 16 kB as the
minimum size before we'll save subfile signatures.  However, short blocks
that are created to store any new chunks needed for a subfile incremental
are always indexed (since we are likely to want to use the same chunks
again in the next backup).

.gitignore update.

Update name of lbs-util program.

Change name of project to Cumulus.

Start changing some references to the LBS name to Cumulus instead.  So far,
changes are in a few of the more user-visible places (name of the
executable, name in the version string).  Many internal references are not
changed, and likely will not be changed immediately (since some of the
changes would change format compatibility).

Hypens are allowed as key names in RFC822-style data.

Update the parsers for the RFC822-style key-value lists.  Allow a hyphen in
key names.  Previously, the "Backup-Intent" field was being ignored because
its name was considered invalid; this change should fix that.

Store unspecified scheme names in database as empty string, not null.

Avoid the use of nulls to represent an unspecified backup scheme in the
local database.  This should fix the bug where database cleaning would not
touch backups without a scheme name.

Delete obsolete sub-block signatures when garbage collecting.

Update NEWS file the 0.7 release.

Note the addition of the sub-file incrementals feature, and include a
script for upgrading the local database to the new format.

Fix a bug in signature loading for sub-file incrementals.

Signatures for sub-file chunks were being written properly, but were not
being loaded properly (signature data and the algorithm string were
being swapped), so no sub-file incrementals were being generated.

Track quantity of data referenced in old segments more precisely.

When calculating used space in segments, treat a reference to just a subset
of data in an object (for example, with subfile incrementals) as using just
that data, instead of the entire object.  This should provide better
information to the segment cleaner.

Initial support for efficient sub-file incrementals.

This is a cleaned-up version of the code written for the OSDI'08
submission to implement sub-file incremental deltas.  Large files are
broken into small chunks (in a content-sensitive manner with Rabin
fingerprints, as in LBFS).  Hash values are computed for the chunks and
stored in a new database table in the local database.  On subsequent
backups, when a file has changed, search for chunks that are identical,
so that portions of old blocks may be re-used even if the entire blocks
cannot be.

Remove some debugging output so backup runs are less verbose.

Put updated copyright statements in all source files.

These now reflect the fact that all code should be distributable under the
GPLv2.

Report compressed size of data written in a backup as well as uncompressed.

When exiting, a summary of the size of all segments (grouped by type: data,
metadata, ...) is printed.  Extend this so that both the uncompressed and
compressed sizes of the segments are printed, and to do so now also keep
track of the compressed size of data.

Update copyright dates in source files.

Squeeze extra blank lines when dumping metadata logs.

In lbs-util, squeeze out extra blank lines in the output of the
read-metadata command.  Extra blank lines may appear in the input,
particularly when delta-encoding metadata logs, but to produce
uniform-looking outputs, delete these extra blank lines.

NEWS updates.

Update arguments passed to upload script.

Fix the remote upload script implementation in lbs so that it matches the
conventions expected by the S3 sample script.

Implement a simple backend script to store data to Amazon S3.

This currently doesn't quite use the interface expected by lbs.  The
interfaces will be matched soon.

Preliminary support for external file upload scripts.

This adds initial support for calling out to an external script to transfer
files to a backup server.  Storage requirements on the client using this
are minimal: space for the local database and for spooling several files
for upload.  Local temporary files are deleted as they are uploaded, and
the backup rate is throttled to the upload rate.

Initial framework for direct transfer of backups to remote storage.

Add a layer of indirection in the writing of files to the backup store, and
create a background thread to handle the processing of files to be stored.
Right now this secondary thread does not do much, but will easily be able
to launch a helper script for transferring data to a remote server.

Files are processed by the background thread one at a time.  Multiple files
can be queued up for processing, but the size of the queue is limited so
that the production of backup data will be throttled to the speed at which
the data can be transferred (to bound the temporary space needed for
storing files).

Make restoring from snapshots more efficient.

When restoring a snapshot, restore files in order roughly determined by how
they are stored in segments, instead of in pure lexicographic order.  This
should ensure that, for the most part, each segment only has to be unpacked
once, instead of perhaps many times as could happen previously, and so
should make restoring more efficient.

This implementation loads all metadata into memory to determine the
ordering, and so restores are now much more memory-intensive than before.
It would be good to work on memory requirements later--either offer an
option to use the old behavior, or perhaps load some of the data into a
temporary database.

Allow restores of just selected files/directories.

Previously, only a complete snapshot could be restored.  This change to
lbs-util will allow just selected data to be restored.

Documentation updates.

Add GPLv2 license conditions.

Since some code is derived from GPL-covered software, allow the entire
program to be distributed under the terms of the GPL, version 2.