README: bup now has more reasons it's cool and fewer not to use it.

Clearly we're making some progress.  I look forward to a world in which
we can finally delete the "reasons bup is stupid" section.

index: if files were already deleted, don't dirty the index.

We had a bug where any deleted files in the index would always dirty all
their parent directories when refreshing, which is inefficient.

cmd-save: don't recurse into already-valid subdirs.

When iterating through the index, if we find out that a particular dir (like
/usr) has a known-valid sha1sum and isn't marked as changed, there's no need
to recurse into it at all.  This saves some pointless grinding through the
index when entire swaths of the tree are known to be already valid.

cmd-index/cmd-save: correctly mark directories as dirty/clean.

Previously, we just ignored the IX_HASHVALID on directories, and regenerated
their hashes on every backup regardless.  Now we correctly save directory
hashes and mark them IX_HASHVALID after doing a backup, as well as removing
IX_HASHVALID all the way up the tree whenever a file is marked as invalid.

drecurse.py: handle initial pathnames that aren't directories.

Fix some list comprehensions that I thought were generator comprehensions.

Apparently [x for x in whatever] yields a list, not an iterator, which means
two things:
  - it might use more memory than I thought
  - you definitely don't need to write list([...]) since it's already a
    list.

Clean up a few of these.  You learn something new every day.

test.sh: don't try non-quick fsck on damaged repositories.

It turns out that older versions of git (1.5.x or so) have a git-verify-pack
that goes into an endless loop when it hits certain kinds of corruption, and
our test would trigger it almost every time.  Using --quick avoids calling
git-verify-pack, so it won't exhibit the problem.

Unfortunately this means a slightly less thorough test of non-quick
bup-fsck, but it'll have to do.  Better than failing tests nonstop, anyway.

Reported by Eduardo Kienetz.

Wrote man pages for bup(1) and all the subcommands.

Merge remote branch 'origin/master'

* origin/master:
  cmd-margin: work correctly in python 2.4 when a midx is present.

cmd-save: fix a potential divide by zero error.

In the progress calculation stuff.

cmd-ls: a line got lost and it didn't work at all.

Also add a trivial test for bup ls to prevent this sort of thing in the
future.

cmd-margin: work correctly in python 2.4 when a midx is present.

And add a test so this doesn't happen again.

Infrastructure for generating a markdown-based man page using pandoc.

The man page (bup.1) is total drivel for the moment, though.  And arguably
we could split up the manpages per subcommand like git does, but maybe
that's overkill at this stage.

bup.py: list subcommands in alphabetical order.

We were forgetting to sort the output of listdir().

bup save: try to estimate the time remaining.

Naturally, estimating the time remaining is one of those things that sounds
super easy, but isn't.  So the numbers wobble around a bit more than I'd
like, especially at first.  But apply a few scary heuristics, and boom!
Stuff happens.

When receiving an index from the server, print a handy progress message.

This is less boring than seeing a blank screen while we download 5+ megs of
stuff.

bup-server: revert to non-midx indexes when suggesting a pack.

Currently midx files can't tell you *which* index contains a particular
hash, just that *one* of them does.  So bup-server was barfing when it
expected MultiPackIndex.exists() to return a pack name, and was getting a
.midx file instead.

We could have loosened the assertion and allowed the server to suggest a
.midx file... but those can be huge, and it defeats the purpose of only
suggesting the minimal set of packs so that lightweight clients aren't
overwhelmed.

Narrow the exception handling in cmd-save.

If we encountered an error *writing* the pack, we were counting it as a
non-fatal error, which was not the intention.  Only *reading* files we want
to back up should be considered non-fatal.

bup index: fix progress message printing when using -v.

It wasn't printing often enough, and thus was absent more often than
present.

On python 2.4 on MacOS X, __len__() must return an int.

We were already returning integers, which seem to be "long ints" in this
case, even though they're relatively small.  Whatever, we'll typecast them
to int first, and now unit tests pass.

Merge branch 'indexrewrite'

* indexrewrite:
  Greatly improved progress reporting during index/save.
  Fix bugs in new indexing code.
  Speed up cmd-drecurse by 40%.
  Split directory recursion stuff from cmd-index.py into drecurse.py.
  Massive speedups to bupindex code.

Greatly improved progress reporting during index/save.

Now that the index reading stuff is much faster, we can afford to waste time
reading through it just to count how many bytes we're planning to back up.

And that lets us print really friendly progress messages during bup save, in
which we can tell you exactly what fraction of your bytes have been backed
up so far.

Fix bugs in new indexing code.

The logic was way too screwy, so I've simplified it a lot.  Also extended
the unit tests quite a bit to replicate the weird problems I was having.  It
seems pretty stable - and pretty fast - now.

Iterating through an index of my whole home directory (bup index -p ~) now
takes about 5.1 seconds, vs. 3.5 seconds before the rewrite.  However,
iterating through just a *fraction* of the index can now bypass all the
parts we don't care about, so it's much much faster than before.

Could probably still stand some more optimization eventually, but at least
the file format allows for speed.  The rest is just code :)

Speed up cmd-drecurse by 40%.

It's now 40% faster, ie. 1.769 seconds or so to go through my home
directory, instead of the previous 2.935.

Still sucks compared to the native C 'find' command, but that's probably
about as good as it's getting in pure python.

Split directory recursion stuff from cmd-index.py into drecurse.py.

Also add a new command, 'bup drecurse', which just recurses through a
directory tree and prints all the filenames.  This is useful for timing
performance vs. the native 'find' command.

The result is a bit embarrassing; for my home directory of about 188000
files, drecurse is about 10x slower:

$ time bup drecurse -q ~
real 0m2.935s
user 0m2.312s
sys 0m0.580s

$ time find ~ -printf ''
real 0m0.385s
user 0m0.096s
sys 0m0.284s

time find ~ -printf '%s\n' >/dev/null
real 0m0.662s
user 0m0.208s
sys 0m0.456s

Massive speedups to bupindex code.

The old file format was modeled after the git one, but it was kind of dumb;
you couldn't search through the file except linearly, which is pretty slow
when you have hundreds of thousands, or millions, of files.  It also stored
the entire pathname of each file, which got very wasteful as filenames got
longer.

The new format is much quicker; each directory has a pointer to its list of
children, so you can jump around rather than reading linearly through the
file.  Thus you can now 'bup index -p' any subdirectory pretty much
instantly.  The code is still not completely optimized, but the remaining
algorithmic silliness doesn't seem to matter.

And it even still passes unit tests!  Which is too bad, actually, because I
still get oddly crashy behaviour when I repeatedly update a large index. So
there are still some screwy bugs hanging around.  I guess that means we need
better unit tests...

cmd-save: add --smaller option.

This makes it only back up files smaller than the given size.  bup can
handle big files, but you might want to do quicker incremental backups and
skip bigger files except once a day, or something.

It's also handy for testing.

midx: the fanout table entries can be 4 bytes, not 8.

I was trying to be future-proof, but it was kind of overkill, since a 32-bit
fanout entry could handle a total of 4 billion *hashes* per midx.  That
would be 20*4bil = 80 gigs in a single midx.  This corresponds to about 10
terabytes of packs, which isn't inconceivable... but if it happens, you
could just use more than one midx.  Plus you'd likely run into other weird
bup problems before your midx files get anywhere near 80 gigs.

cmd-midx: correctly handle a tiny nonzero number of objects.

If all the sha1sums would have fit in a single page, the number of bits in
the table would be negative, with odd results.  Now we just refuse to create
the midx if there are too few objects *and* too few files, since it would be
useless anyway.

We're still willing to create a very small midx if it allows us to merge
several indexes into one, however small, since that will still speed up
searching.

Use a heapq object to accelerate git.idxmerge().

This greatly accelerates bup margin and bup midx when you're iterating
through a large number of packs.

cmd-margin: a command to find out the max bits of overlap between hashes.

Run 'bup margin' to go through the list of all the objects in your bup
directory and count the number of overlapping prefix bits between each two
consecutive objects.  That is, fine the longest hash length (in bits) that
*would* have caused an overlap, if sha1 hashes had been that length.

On my system with 111 gigs of packs, I get 44 bits.  Out of a total of 160.
That means I'm still safe from collisions for about 2^116 times over.  Or is
it only the square root of that?  Anyway, it's such a large number that my
brain explodes just thinking about it.

Mark my words: 2^160 ought to be enough for anyone.

Update README.md to reflect recent developments.

- Remove the version number since I never remember to update it
- We now work with earlier versions of python and MacOS
- There's now a mailing list
- 'bup fsck' allows us to remove one of the things from the "stupid" list.

Move testfile[12] into t/

Since they're only used for testing, they belong there, after all.

fsck: add a -j# (run multiple threads) option.

Sort of like make -j.  par2 can be pretty slow, so this lets us verify
multiple files in parallel.  Since the files are so big, though, this might
actually make performance *worse* if you don't have a lot of RAM.  I haven't
benchmarked this too much, but on my quad-core with 6 gigs of RAM, -j4 does
definitely make it go "noticeably" faster.

Basic cmd-fsck for checking integrity of packfiles.

It also uses the 'par2' command, if available, to automatically generate
redundancy data, or to use that data for repair purposes.

Includes handy unit test.

cmd-damage: a program for randomly corrupting file contents.

Sure, that *sounds* like a terrible idea.  But it's fun for testing recovery
algorithms, at least.

Use mkstemp() when creating temporary packfiles.

Using getpid() was an okay hack, but there's no good excuse for doing it
that way when there are perfectly good tempfile-naming functions around
already.

rewire a try/finally with a yield inside to be compatible with python 2.4

Apparently you can't put a 'yield' inside a try/finally in older versions of
python.  lame.

client: fix a race condition when the server suggests an index.

If we finished our current pack too quickly after getting the suggestion,
the client would get confused, resulting in 'exected "ok, got %r' type
errors.

cmd-ls and cmd-fuse: toys for browsing your available backups.

'bup ls' lets you browse the set of backups on your current system.  It's a
bit useless, so it might go away or be rewritten eventually.

'bup fuse' is a simple read-only FUSE filesystem that lets you mount your
backup sets as a filesystem (on Linux only).  You can then export this
filesystem over samba or NFS or whatever, and people will be able to restore
their own files from backups.

Warning: we still don't support file metadata in 'bup save', so all the file
permissions will be wrong (and users will probably be able to see things
they shouldn't!).  Also, anything that has been split into chunks will show
you the chunks instead of the full file, which is a bit silly.  There are
also tons of places where performance could be improved.

But it's a pretty neat toy nevertheless.  To try it out:

   mkdir /tmp/backups
   sudo bup fuse /tmp/backups

cmd-midx: some performance optimizations.

Approximately doubles the speed of generating indexes.

cmd-midx: add --auto and --force options.

Rather than having to list the indexes you want to merge, now it can do it
for you automatically.  The output filename is now also optional; it'll
generate it in the right place in the git repo automatically.

When there are multiple overlapping .midx files, discard redundant ones.

That way if someone generates a .midx for a subset of .idx files, then
another for the *entire* set of .idx files, we'll automatically ignore the
former one, thus increasing search speed and improving memory thrashing
behaviour even further.

MultiPackIndex: use .midx files if they exist.

Wow, using a single .midx file that merges my 435 megs of packfile indexes
(across 169 files) reduces memory churn in memtest.py by at least two orders
of magnitude.  (ie. we need to map 100x fewer memory pages in order to
search for each nonexistent object when creating a new backup)  memtest.py
runs *visibly* faster.

We can also remove the PackBitmap code now, since it's not nearly as good as
the PackMidx stuff and is now an unnecessary layer of indirection.

cmd-midx: a command for merging multiple .idx files into one.

This introduces a new "multi-index" index format, as suggested by Lukasz
Kosewski.

.midx files have a variable-bit-width fanout table that's supposedly
optimized to be able to find any sha1 while dirtying only two pages (one for
the fanout table lookup, and one for the final binary search).  Each entry
in the fanout table should correspond to approximately one page's worth of
sha1sums.

Also adds a PackMidx class, which acts just like PackIndex, but for .midx
files.  Not using it for anything yet, though.  The idea is to greatly
reduce memory burn when searching through lots of pack files.

Rename chashsplit.so to _hashsplit.so.

Looks like the python standard is _modulename.so when making a C helper for
a module named modulename.py, so let's do it that way.

Also get rid of the annoying "module" suffix in the .c's filename.  Not sure
why I ever thought that was needed.

Making a warning in chashsplitmodule.c go away.

toplevel exit() doesn't work in python 2.4.

Use sys.exit() instead.

Minor changes to make bup work with git as far back as 1.5.3.1.

In some versions of python, comparing buffers with < gives a warning.

It seems to be a buggy warning.  But we only really do it in one place, and
buffers in question are only 20 bytes long, so forcing them into strings
seems harmless enough.

Wrap mmap calls to help with portability.

python2.4 in 'fink' on MacOS X seems to not like it when you pass a file
length of 0, even though that's supposed to mean "determine map size
automatically."

Makefile: build module using python distutils instead of manually.

This makes it work with fink's version of python, among possibly other
things.

So now we can build chashsplit.so even on MacOS X tiger, even though tiger's
python 2.3 is too old, by installing fink's python24 package first.

executable files: don't assume python2.5.

The forcing of version 2.5 was leftover from before, when it was
accidentally selecting python 2.4 by accident on some distros when both
versions are installed.  But actually that's fine; bup works in python 2.4
without problems.

So let's not cause potentially *more* portability problems by forcing python
2.5 when it might not exist.

Makefile: oops, all the $^ and $< were backwards.

Not that it mattered, since all our files only had one dependency each.  But
it causes confusion if you ever add extra ones.

Make README a symlink to README.md

So as not to confuse anyone who has linked to the README file on github in
the past.

Minor README format changes to make it markdown-compliant.

That way it looks prettier on github.

Change t/tindex.py to pass on Mac OS.

It turns out /etc is a symlink (to /private/etc) on Mac OS, so checking
that the realpath of t/sampledata/etc is /etc fails.  Instead we now check
against the realpath of /etc.

Use a PackBitmap file as a quicker way to check .idx files.

When we receive a new .idx file, we auto-generate a .map file from it.  It's
essentially an allocation bitmap: for each 20-bit prefix, we assign one bit
to tell us if that particular prefix is in that particular packfile.  If it
isn't, there's no point searching the .idx file at all, so we can avoid
mapping in a lot of pages.  If it is, though, we then have to search the
.idx *too*, so we suffer a bit.

On the whole this reduces memory thrashing quite a bit for me, though.
Probably the number of bits needs to be variable in order to work over a
wider range of packfile sizes/numbers.

memtest.py: a standalone program for testing memory usage in PackIndex.

The majority of the memory usage in bup split/save is now caused by
searching pack indexes for sha1 hashes.  The problem with this is that, in
the common case for a first full backup, *none* of the object hashes will be
found, so we'll *always* have to search *all* the packfiles.  With just 45
packfiles of 200k objects each, that makes about (18-8)*45 = 450 binary
search steps, or 100+ 4k pages that need to be loaded from disk, to check
*each* object hash.  memtest.py lets us see how fast RSS creeps up under
various conditions, and how different optimizations affect the result.

options parser: automatically convert strings to ints when appropriate.

If the given parameter is exactly an int (ie. str(int(v)) == v) then convert
it to an int automatically.  This helps avoid weird bugs in apps using the
option parser.

cmd-save: if verbose==1, don't bother printing unmodified names.

That just clutters the output; clearly what people *really* want to see is
the list of files we're actually modifying.

But if you want more, increase the verbosity and you'll get more.

client-server: only retrieve index files when actually needed.

A busy server could end up with a *large* number of index files, mostly
referring to objects from other clients.  Downloading all the indexes not only
wastes bandwidth, but causes a more insidious problem: small servers end up
having to mmap a huge number of large index files, which sucks lots of RAM.

In general, the RAM on a server is roughly proportional to the disk space on
that server.  So it's okay for larger clients to need more RAM in order
to complete a backup.  However, it's not okay for the existence of larger
clients to make smaller clients suffer.  Hopefully this change will settle
it a bit.

Reduce default max objects per pack to 200,000 to save memory.

After some testing, it seems each object sha1 we need to cache while writing
a pack costs us about 83 bytes of memory.  (This isn't so great, so
optimizing it in C later could cut this down a lot.)  The new limit of 200k
objects takes about 16.6 megs of RAM, which nowadays is pretty acceptable.
It also corresponds to roughly 1GB of packfile for my random select of
sample data, so (since the default packfile limit is about 1GB anyway), this
*mostly* won't matter.

It will have an effect if your data is highly compressible, however; an
8192-byte object could compress down to a very small size and you'd end up
with a large number of objects.  The previous default limit of 10 million
objects was ridiculous, since that would take 830 megs of RAM.

split_to_blob_or_tree was accidentally not using the 'fanout' setting.

Thus, 'bup save' on huge files would suck lots of RAM.

cmd-server: receive-objects should return a relative, not absolute, path.

Update the README to reflect recent changes.

Merge branch 'cygwin'

* cygwin:
  Assorted cleanups to Luke's cygwin fixes.
  Makefile: work with cygwin on different windows versions.
  .gitignore sanity.
  Makefile:  On Windows, executable files must end with .exe.
  client.py:  Windows files don't support ':', so rename cachedir.
  index.py:  os.rename() fails on Windows if dstfile already exists.
  Don't try to rename tmpfiles into existing open files.
  helpers.py:  Cygwin doesn't support `hostname -f`, use `hostname`.
  cmd-index.py:  Retry os.open without O_LARGEFILE if not supported.
  Makefile:  Build on Windows under Cygwin.

Assorted cleanups to Luke's cygwin fixes.

There were a few things that weren't quite done how I would have done them,
so I changed the implementation.  Should still work in cygwin, though.

The only actual functional changes are:
 - index.Reader.close() now actually sets m=None rather than just closing it
 - removed the "if rename fails, then unlink first" logic, which is
   seemingly not needed after all.
 - rather than special-casing cygwin to use "hostname" instead of "hostname
   -f", it turns out python has a socket.getfqdn() that does what we want.

Makefile: work with cygwin on different windows versions.

Just check the CYGWIN part; don't depend on the fact that it's NT 5.1.  (Of
course, uname isn't supposed to report such things by default anyway... but
that's cygwin for you.)

Merge branch 'master' of git://github.com/apenwarr/bup

.gitignore sanity.

Makefile:  On Windows, executable files must end with .exe.

client.py:  Windows files don't support ':', so rename cachedir.

Cachedir was previously $host:$dir, and is now $host-$dir.

index.py:  os.rename() fails on Windows if dstfile already exists.

Hence, we perform an os.unlink on the dstfile if os.rename() receives
an OSError exception, and try again.

Don't try to rename tmpfiles into existing open files.

Linux and friends have no problem with this, but Windows doesn't allow
this without some effort, which we can avoid by... not needing to write
to an already-open file.

Give index.Reader a 'close' method which identifies and closes any open
mmaped files, and make cmd-index.py use this before trying to close a
index.Writer instance (which renames a tmpfile into the same file the
Reader has mmaped).

helpers.py:  Cygwin doesn't support `hostname -f`, use `hostname`.

cmd-index.py:  Retry os.open without O_LARGEFILE if not supported.

Python under Cygwin doesn't have os.O_LARGEFILE, so if we receive an
'AttributeError' exception trying to open something, just remove
O_LARGEFILE and try again.

Makefile:  Build on Windows under Cygwin.

- Python modules have to end with .dll instead .so to load into Python
  via 'import'.
- GCC under Windows builds all programs with -fPIC, and doesn't accept
  this command-line option.
- libpython2.5.dll is found in /usr/bin under Cygwin (wtf?), so we need
  to add this to the LDFLAGS path.
- 'make clean' should remove .dll files too.

Oops, 'bup save /' produced an invalid tree.

Add a bunch of assertions to make sure that never happens.

This adds the long-awaited indexfile feature, so you no longer have to feed
your backups through tar.

Okay, 'bup save' is still a bit weak... but it could be much worse.

Merge branch 'indexfile'

* indexfile:
  Minor fix for python 2.4.4 compatibility.
  cmd-save: completely reimplement using the indexfile.
  Moved some reusable index-handling code from cmd-index.py to index.py.
  A bunch of wvtests for the 'bup index' command.
  Start using wvtest.sh for shell-based tests in test-sh.
  cmd-index: default indexfile path is ~/.bup/bupindex, not $PWD/index
  cmd-index: skip merging the index if nothing was written to the new one.
  cmd-index: only update if -u is given; print only given file/dirnames.
  cmd-index: correct reporting of deleted vs. added vs. modified status.
  Generalize the multi-index-walking code.
  cmd-index: indexfiles should start with a well-known header.
  cmd-index: eliminate redundant paths from index update command.
  cmd-index: some handy options.
  index: add --xdev (--one-file-system) option.
  Fix some bugs with indexing '/'
  cmd-index: basic index reader/writer/merger.

Minor fix for python 2.4.4 compatibility.

cmd-save: completely reimplement using the indexfile.

'bup save' no longer walks the filesystem: instead it walks the indexfile
(which is much faster) and doesn't bother opening any files that haven't had
an attribute change, since it can just reuse their sha1 from before.  That
makes it *much* faster in the common case.

Moved some reusable index-handling code from cmd-index.py to index.py.

A bunch of wvtests for the 'bup index' command.

Start using wvtest.sh for shell-based tests in test-sh.

This makes the output a little prettier... at least in the common case where
it passes :)

cmd-index: default indexfile path is ~/.bup/bupindex, not $PWD/index

cmd-index: skip merging the index if nothing was written to the new one.

cmd-index: only update if -u is given; print only given file/dirnames.

cmd-index now does two things:
 - it updates the index with the given names if -u is given
 - it prints the index if -p, -s, or -m are given.

In both cases, if filenames are given, it operates (recursively) on the
given filenames or directories.  If no filenames are given, -u fails (we
don't want to default to /; it's too slow) but -p/s/m just prints the whole
index.

cmd-index: correct reporting of deleted vs. added vs. modified status.

A file with an all-zero sha1 is considered Added instead of Modified, since
it has obviously *never* had a valid sha1.  (A modified file has an old
sha1, but IX_HASHVALID isn't set.)

We also now don't remove old files from the index - for now - so that we can
report old files with a D status.  This might perhaps be useful eventually.

Furthermore, we had a but where reindexing a particular filename would
"sometimes" cause siblings of that file to be marked as deleted.  The
sibling entries should never be updated, because we didn't check them and
thus have no idea of their new status.  This bug was mostly caused by the
silly way we current pass dirnames and filenames around...

Generalize the multi-index-walking code.

Now you can walk through multiple indexes correctly from anywhere, avoiding
the need for merging a huge index just to update a few files.

cmd-index: indexfiles should start with a well-known header.

cmd-index: eliminate redundant paths from index update command.

If someone asks to update "/etc" and "/etc/passwd", the latter is redundant
because it's included in the first.  Don't bother updating the file twice
(and thus causing two index merges, etc).

Ideally we would only do one merge for *any* number of updates (etc /etc and
/var).  This should be possible as long as we sort the entries correctly
(/var/ and then /etc/), since a single sequential indexfile could just have
one appended to the other.  But we don't do that yet.

cmd-index: some handy options.

New options:
--modified: print only files that aren't up to date
--status: prefix printouts with status chars
--fake-valid: mark all entries as up to date
--indexfile: override the default index filename

index: add --xdev (--one-file-system) option.

For not traversing across filesystem boundaries.

Fix some bugs with indexing '/'

cmd-index: basic index reader/writer/merger.

On MacOS X, "wc -l" returns extra whitespace.

ie. "    0" instead of "0".

The easiest workaround is to compare as a number instead of as a string.
This seems to work correctly on both MacOS and Linux.

More compile options for MacOS X.

Based on a patch from Dave Coombs.  I changed it to auto-detect the OS
platform, so I might have broken it, however.

splitting to a remote server would cause "already busy" errors.

Specifically:
client.ClientError: already busy with command 'receive-objects'

That's because recent changes removed the call to onclose() from
PackWriter_Remote.  Now it's back, plus I added an extra unit test to reveal
the problem.

client: enhance the PATH when searching for the 'bup' binary.

Automatically adds the *local* $PWD to the *remote* $PATH before trying to
run 'bup server'.  That way, if you build the source in exactly the same
folder on two machines - or if those two machines are actually the same
machine and you're just doing a test against localhost - it'll work.

I hereby curse both "sh -c <command>" and "ssh hostname -- <command>" for
not allowing a sensible way to just set argv[] without doing any stupid
quoting.  Nasty.