Drop dependence on libtar.

Implement everything we need to write TAR files ourself; this isn't too
difficult since we are only ever writing regular files with fixed-length
filenames (so need to worry about long file names).  In fact, doing it
directly is really no more complicated than using libtar.

Update the format documentation to describe the current backup format.

The old documentation referred to the old binary backup format, and was
incomplete at that.  Rewrite it to discuss the current format, including a
discussion of segment/object storage, object references, the format of the
metadata listing, and the root backup descriptor.

The documentation can be improved, and some parts are certainly a bit
spotty, but this gives a good quick overview of the entire format.

Print a help message if no paths are specified to back up.

Rather than defaulting to backing up the current directory, always require
that a path be specified.  If no paths are specified, print the usage
message and exit.

Also, fix a crash that previously occurred when no paths were specified.

Update .gitignore: explicitly ignore .o files.

Provide a more detailed indication of file status when backing up.

Indicate whether a file is new, or whether we managed to find the old data
in other segments, or whether data is being copied because we are cleaning
segments, etc.

URI-escape the '@' character.

Ensure that the '@' character is escaped in strings.  This isn't necessary
now, but in the future this might be useful so that indirect references are
never ambiguous.  (If a "@" appears, it's an indirect reference; if a
literal "@" is needed, it is escaped.)

Include scheme name in statcache file, so localdb directory can be shared.

Add support for octal, hexadecimal in restore.pl script.

Do not warn when fewer than two arguments are provided.

It used to be that a source and destination had to be provided as the last
two arguments.  The use of the --dest= option now makes that not true, so
don't print a usage message and exit when only a single source is provided.

Update the descriptor format string to "v0.2".

The introduction of octal probably makes this fair.

Really fix the umask problem.

The fix in bf947741ac8f65e74d594a1e14e94d90320b403e didn't entirely work.
This should be better.

Add support for octal and hexadecimal output in dumps.

Switch to using octal for file modesin metadata listings, since this is
more readable.

Rename --name to --scheme, and store the scheme name in the local database.

Add a --name command-line option for naming snapshots.

This feature is meant to support storing several separate sets of snapshots
in the same directory--for example, snapshots of multiple computers, or
snapshots of different sets of directories.  These snapshots can be deleted
independently.  The snapshots will be permitted to share segments.

A name is simply applied for management convience, to help in
distinguishing the different sets of backups.  The string specified with
--name is included both in the snapshot descriptor filename and as a
"Name:" field within that descriptor.

Respect umask when creating backup files.

Previously backup files were created with permissions of 0600 before the
umask was subtracted.  Set it to 0666 now; the user can adjust the
permissions to make them more restrictive by changing the umask or
permissions in the parent directories.

Reorganize filesystem traversal and dumping code.

Work to more cleanly separate the parts of the code that scan the
filesystem from the parts which actually generate dump data to the backup
snapshot.

Slightly improve error-handling during backups.

Makefile cleanups.

Rename format.{cc,h} -> util.{cc,h}.

Extract major/minor components of device numbers.

I hope these are the right macros and include files to use...

Dump the device number of character/block devices.

Auto-generate a version number for the program with git-describe.

If compiled from a git repository, embed the version number (output from
git-describe) into the resulting binary.  If this does not work for
whatever reason, the version string embedded is "Unknown".

Add string un-escaping, and fix the statcache reader to use it.

Rename the generated executable from "scandir" to "lbs".

Implement a more complex inclusion/exclusion system for files.

Allow multiple paths to be specified for backups, to allow different parts
of the filesystem tree to be selected for backup in a single snapshot.

Fix a bug in statcache support for file sizes.

This had the effect of renderig the statcache useless (all files would be
entirely read), but apart from the performance issue should have caused any
problems.

When comparing a file against the stat cache, check size field too.

Dump statistics of data written at the end of a backup run.

Include file size in the stat cache (but do not check against it yet).

Rewrite object reference parser.

This new version should handle all options, including checksums and object
ranges, though it hasn't been fully tested.

Only trust the results of a stat if two separate backups agree.

This should eliminate races where stat information might not change if
there are two changes to a file within the same second--as long as two
backups are not taken less than a second apart.

Sort-of-working statcache implementation.

This will use stat information to determine when a file doesn't need to
be read again.  There are still some bits left to be implemented; in
particular, parsing of references needs to be fixed, since at the moment
checksums and ranges aren't supported, and any files using them will
have block lists corrupted by the stat cache.  (Fortunately, nothing
uses those reference forms yet for file contents.)

Write the backup descriptor as the very last step in a backup.

For consistency, we should make sure that all segments and other data
needed to reconstruct a backup are written before we write out the
backup descriptor file itself.

Try an alternate segment cleaning ordering.

This one gives more weight to expiring nearly-empty segments.

Add a simple script for garbage collecting old segments.

Preserve the "timestamp" database field when expiring segments.

When segments are repacked, we would like to keep the original timestamp
for the old objects which are written into new segments.  These changes
should now propagate that timestamp value.

Minor formatting fix when outputting the statcache file.

Partial commit of statcache support.

This will cache the results of stat calls from previous backups, so that
future backups do not need to read the files in their entirety if no data
has changed.

Rename descriptor files.

Prefix them with "snapshot-", so they will sort after all segment files.

Wait to write the backup description until a backup is finished.

Update database schema with views for choosing segments to clean.

Create a couple of database views, one for gathering summary statistics
about segments in use, and one for ranking segments to be cleaned and
rewritten, based on utilization and the age of the data contained in it.

Fix --localdb= option.

Factor code to prepare SQLite statements into a separate function.

This cuts down on a little code duplication and also makes it easy to
include SQL statements in inline strings when they are prepared.

Also, switch to the older sqlite3_prepare interface (not _prepare_v2) since
the new interface is still a bit too new to be commonly available.

Fix typo.

Make segment compression/encryption filter to command-line-selectable.

Design note: grouping also allows better compression.

Create an SQL script for cleaning out the local object database.

Make parser in restore.pl more tolerant, and reorder descriptor fields.

Add version information to the backup descriptor files.

This adds a "Format:" line at the start of a backup descriptor, with the
intent that different formats can be recognized if there is a need to make
changes in the future.  This can also be used as a magic number to identify
LBS snapshot files.

Also, update the restore.pl script to handle the new format--make the
parser more flexible so that fields can appear in any order, and
unrecognized lines are ignored.

Do not bother to split indirect block lists into a separate segment.

For now, just group them with the rest of the metadata.  It's not worth
splitting them up now; this could be reverted later.

Differentiate between never-before-seen objects and seen-but-expired.

We group seen-but-expired objects into different segments, since the fact
that the content has been seen before is an indicator that the data is
long-lived, and grouping by (expected future) age should help increase
segment utilization.

Check for errors when files are opened for dumping.

Before, we could fail to open a file when O_NOATIME was specified but the
file was owned by another user, and we didn't notice this.  Now we do, and
we also retry the open without O_NOATIME.

Output filename to metadata log after fully processing file.

Previously, if there was an error processing the file, the metadata
dictionary was not output, but the filename was, producing an incorrect
metadata file.  This is now fixed.

Slightly expand the set of characters which are escaped in filenames.

Use NULL in the local database to indicate that blocks are not expired.

Extend local database once more.

This should hopefully add most of the features needed for the moment.
Improvements made:
  - Normalize segment names by putting them in a separate table and
    referring to them by ID everywhere else.  This should help quite a bit,
    since segment names are ~36 characters long.  Add conversion functions
    to the C++ code, which aren't optimized yet (we should cache results in
    the C++ code and not re-query the database each time).
  - Similarly, normalize snapshot names.
  - Add an expired field to the object index, so that we can stop using
    objects in future backups but still remember how old the data is.
Some more work is still needed in the C++ code, but the hope is that the
database schema itself will be more stable now.

Add (probably long-overdue) .gitignore file.

Add rudimentary command-line parsing and support for file exclusions.

Bugfix in size estimates for filtered tarfile outputs.

Bugfix for restore.pl.

Indirect references to data blocks were not being properly handled, so
large files (those using an indirect reference to the data) were not
restored properly.

This was at least caught by the checksums, so no data was ever silently
corrupted.

Add timestamps to block when they are inserted into the local database.

Handle new-style user/group entries in the restore script.

The new style is
    uid (username)
and was previously causing a warning since the entire string is not
numeric, just the first part.  Now explicitly split it apart.  (For now, we
ignore the username string, but it could possibly be used in the future.)

Initial support for filtering TAR files through an external program.

At the moment this is hard-coded to pipe data through "bzip2 -c", but
this should be made flexible later.

Track which objects are used in which snapshots in the local database.

Debugging message cleanup.

Initial cut at re-using objects from old segments when contents match.

Keep an index of old stored blocks, using sqlite3.

Link sqlite3 in with the snapshot program, and start to write a wrapper
around a "local database" which tracks previously-backed-up data to make
incremental backups possible.

At the moment, blocks are indexed as they are stored, but we never read
from the index, so blocks are not yet reused.

Start writing up some design notes for LBS.

Try to explain the rationale for the chosen design, and explain some of the
other designs that were considered and rejected.

Ensure filesize written to metadata log matches number of bytes dumped.

Various minor tweaks to the metadata format.

Use a timestamp in generating the descriptor filename.

Also include the timestamp (in a more readable format) in the descriptor
file itself.

Disable debugging output for the reference restore program.

Most of the debugging can be turned on by setting $VERBOSE = 1;

Actually recreate files in the snapshot.

With this change, the prototype restore tool is essentially functional.
Special files are still not properly handled, and there are a few other
limitations, but for the most part it all works.

Add in decoding (URI-style, %xx) of filenames to reference decoder.

Continue work on reference decoder.

  - Add code to parse metadata sections (including following indirect
    pointers).
  - Add code to parse data block listings (including indirect pointers).
  - Verify checksums on all files.

Primarily left: actually write restored file contents out to the
filesystem.

Begin work on a reference decoder for backups.

The intent is that the reference decoder will eventually be a tool for
recovery, if need, before a better tool is written.  It should also help to
verify the format specification and backup tool.

The reference decoder can currently parse a single object reference and
extract the data for it.

Write backup descriptor to a file, not stdout.

The backup descriptor names the object at the root of the snapshot, and
lists all the segments needed.  The filename used is currently fixed,
though, and should later be based on the current time.

Clean up error reporting.

Use larger metadata blocks, and don't output type field twice.

Debugging output cleanup.

Allow metadata to be written incrementally.

Remove checksums and reference tracking; I think they are not needed.

A few minor adjustments to the ObjectReference interface.

Add a new object-oriented wrapper for building object references.

Miscellaneous changes.

  - Disable profiling output for now.  It can be turned on again later.
  - Allow destination directory for backup files to be specified on the
    command-line (but we should add proper command-line parsing later).
  - More work to track inter-object references, but not yet finished.

Start work on a more object-oriented interface for creating objects.

Rename tarstore -> store, since it is the only implementation now.

Remove old store implementation.

Partial support for tracker inter-object references.

Add indrect objects for listing contents of large files.

Remove code using old segment writer.

All writes should now happen to TAR-format segments, and data should be
serialized as text.

Automatically split segments to meet size targets.

Add URI-style escaping of filename characters.

Remove early test code for the tarfile storage backend.

Reduce debugging output.

Add checksums to tarstore, and partially migrate to using it for storage.

Each tarfile segment gets a file called "checksums" now which contains
SHA-1 hashes of all objects contained in it.  There is currently no
checksum computed for the checksum file itself.

Begin migrating scandir to using the tar-based storage for backups.
Backups in the old format are still written, and there is still some
other cleanup to be done, but most of the raw data is currently handled.

Begin work on an alternate object store mechanism using the TAR format.

Each segment is placed in a separate file, and each object is a file stored
within that TAR archive.  libtar is used to write (and perhaps later read)
tar files.

Tag objects with a 4-byte type code.

Return the names for allocated objects, and link file metaata to data.

Extend the interface for the new_object methods so that they can return the
segment UUID and object index for created objects.  Then, use this to write
out links from the file metadata to the data blocks making up the file, via
an indirect block.

Support for spreading objects across segments.

New segments are created automatically whenever an old segment becomes too
large (current limit is set at something over 1 MB, but this could be
adjusted).