Space management

On an archive filesystem with fixed space, perhaps we want to free up just enough space to make one more backup.

This seems to mean:

1. Estimate how much space the new backup will take. There are several approaches with differing cost and accuracy. Any are potentially useful.

   1. This can be done precisely, but very laboriously, by checking which files are new/changed, hashing and then compressing their blocks, and seeing how much space will be needed. We need to check whether the new hashes match either already-stored blocks, or blocks that would have been written earlier in this backup (but that actually have not been.) Also, we could build, compress, and discard, new indexes.

   2. Or, somewhat cheaper (in CPU), assume the new blocks are incompressible, but do hash them to see which blocks are new

   3. Or, cheaper and tending to overestimate by even more, just see which files are new/changed and assume all their data is new.

2. Free up x MB of space. This feature is also useful in itself.

   1. We need an order in which to delete old versions: most simply just FIFO but we could also thin out the history and keep less-frequently-spaced versions.

   2. Determine how much space would be removed by deleting a set of versions, ideally in a way where it's cheap to calculate how that changes as we delete more and more versions. This can be done from a relation between versions and block hashes. Perhaps there's a representation that makes the successive subtraction of more versions fast. Perhaps block hashes should be interned in memory.

   3. Show this to the user.

   4. Delete them.