Things to do for image*:

1. Checksum chunks or the entire image file?
   Maybe just as a debug option to check for bugs in the zipper itself.
   In general use, we will be using TCP as the transport for image files
   or we will be using frisbee and the UDP checksum in conjunction with
   frisbee itself tracking blocks should be sufficient.  Anyway, doing
   an entire image checksum would be complicated by frisbee's out of order
   receipt of chunks.

2. Imagezip could be multithreaded so that we can be reading ahead on the
   input device and overlapping IO with compression.  Maybe a third thread
   for doing output.  Input is a little tricky since imagezip shortens up
   its reads as it gets near the end of a chunk, so the buffer mechanism
   will have to handle having blocks only partially consumed.

3. In imagezip, split out the FS-specific code into subdirectories.
   [DONE]

4. Write an imageconvert so that we can convert old version images into
   new ones and maybe change the compression level used in an image.

5. Imageunzip could be triple-threaded like frisbee, i.e., split the
   file reading and decompression that are currently one in imageunzip.

6. Image hashing and "delta" images.
   [ DONE -- as a separate program, imagehash.  It would be more efficient
     to have imagezip create the signature as it goes. ]
   [ DONE -- imagezip now can create the signature "as it goes". But it
     makes an extra read of the disk data to do it. This could be further
     optimized to compute the hash as it reads/compresses the data. ]
   Create a "signature" file for an image using a collision-resistant hash
   like MD5 or SHA-1.  This signature could be used to create incremental
   (delta) images based on a full image. See TODO.hash for more.

7. Add an option to exclude (skip) disk blocks outside of any DOS partition.
   By default, we want to include these blocks in the image since some
   systems stash magic info this way (IBM laptops for instance).  But in
   some cases we want to ignore it.  Since the MBR often falls in the
   outside-of-any-partition category (e.g., DOS partition 1 starting at
   sector 63, aka cylinder 1), we may need to further break this down into
   "before first part", "between parts", "after last part".  Also need an
   option to exclude space outside a filesystem but inside a DOS partition
   (e.g., when creating a small filesystem in a large partition).  This is
   highly dependent on the filesystem type, but presumably we can easily
   detect space beyond the end of the FS.  "Before the start" probably
   doesn't make sense for most filesystems.  Hmm...for FFS we can detect
   space outside a BSD partition in addition to space beyond the end of
   a filesystem but inside the BSD partition.  Yuk!  Maybe we keep it
   simple and have a single option and just treat things like the MBR
   special.

8. Encrypted images or encrypted transfer of images.
   [ DONE. See:
     http://www.cs.utah.edu/flux/papers/frisbeesec-cset08-base.html ]
   Depends on what we want.  By encrypting the image itself, we protect
   confidentiality while on disk and lessen the CPU usage of the frisbee
   server.  A possible concern is that, once a user has received an image,
   they know the key.  If we were to use symmetric crypto, they would be
   able, at some future time, to spoof the contents of the image as it
   is being sent to others.  But that is not the point of encrypting the
   contents, the point is to prevent unauthorized people from seeing the
   contents, and if you have already received the image, you are clearly
   authorized.  Even so, we could prevent the problem by using asymmetric
   crypto.

   If we instead say that we are mostly concerned about secure transfer
   of images (with confidentiality of images in the filesystem done with
   filesystem mechanisms) then we could encrypt images as they are sent
   on a per session basis.  This could be hideously expensive for the
   frisbee server.

   Either way, the frisbee protocol will need some block-by-block
   authentication mechanism to ensure integrity.  It has to be per-block
   and not per-chunk since it is the block header which contains the info
   on what chunk a block belongs to and in what order the blocks should
   be reassembled in to reform the chunk.

   Imagezip would take as an argument a key (or a file from which to read
   the key?).  We can perform the encryption either before or after
   compression.  I'm not sure of the impact on image size, but I suspect
   that encrypting first might make compression less effective.  Doing
   it before would also result in an image in which each chunk's meta-data
   (header info: disk ranges contained, any relocations) is not encrypted.
   Is this a problem?  The block ranges and relocations could give some
   hint as to what the image contains (e.g., if block 16 is not in the
   list, it isn't a BSD filesystem since that is where the superblock is).
   We can independently encrypt the header if necessary.  But it would
   probably be better to just wait til a chunk has been fully assembled,
   including the meta-data, and then encrypt it all before we write it
   to the image file (ugh, but will this change the size of the chunk?)

   Imageunzip (and frisbee) will likewise take a new argument for the key
   to be used.  For frisbee this will be transferred "out-of-band" with
   TMCD.  While decryption could take place in a separate thread, I'm
   inclined not to worry about it right now given that we are mostly working
   with uniprocessor machines where there would be no advantage.  Anyway,
   imageunzip would receive blocks, verify them, and assemble them into
   chunks, decompress and decrypt (or visa-versa) the chunks, and feed
   them to the disk writer.

9. Recognize unused filesystem metadata blocks.
   [ DONE -- sorta, for UFS2 using the -M option. In imagezip, we identify
     free inodes and zero them except for the generation number. So they
     are still in the image, but mostly zero. ]
   Right now we pretty much leave FS metadata structures alone and thus
   consider them allocated, we might be able to improve on that.  In
   particular, free UNIX-like inode data structures consume a lot of space.
   However, free inodes still need to have some initialized fields, at
   the very least, the mode field needs to be zero.  But we could create
   a relocation-type for inode blocks, telling imageunzip that a particular
   block range consists of unused inodes and that it should zero those
   blocks rather than just skip them.  The downside is that there are a lot
   of different inode layouts, and that is a lot of specific knowledge for
   imageunzip.  We could get away with a generic relocation that just says
   zero this block range.  Some BSDs like to randomize the initial generation
   number on an inode though, so this would not work for that.  But I could
   imagine a relocation type that says "place X-bytes of random data every
   Y bytes starting at offset Z in this range".  I can imagine it, but I
   just cannot bring myself to do it!  At any rate, I'm not sure the saving
   vs. complexity trade-off is in our favor here.

   A quick check: our FreeBSD image consists of 3 filesystems.  Let's just
   consider /usr (a 2GB filesystem) which has 23552 inodes per cylinder group
   with 12 cylinder groups.  Each inode is 128 bytes so that is 36 (decimal)
   megabytes of which about 80% are free.  Allowing for scattering of the
   allocated inodes, we could still have upwards of 20MB of free blocks of
   inodes.

10. Treat zero blocks special.
   This is prompted by the zero-this-range relocation postulated in #9.
   There might be value is distinguishing block ranges that must be zero
   (e.g., allocated data blocks that contain all zeros, or free inode blocks
   that require certain fields to be zero) and just note them in the image
   header range data.  Maybe save as a relocation type as above or just as
   a distinguished allocated range type.  The question is whether we can
   efficiently recognize such blocks and whether we ultimately save space
   over just allowing zlib to compress the data (presumably blocks of zeros
   compress really well!)

11. Death to bubble sort and singly-linked lists.
   [ DONE -- for bubble sort, in a wicked hacky way. If USE_HACKSORT is
     defined we keep a separate array of pointers to range data structures
     that we can call qsort on. ]
   We represent the set of free and allocated blocks with a singly-linked
   list.  The process is:

     * Start with an empty "skips" (free) list.
     * As we traverse all FSes on a disk, we identify free block ranges
       which are appended to the skips list.
     * The list is then sorted and abutting ranges merged.
       We apply an optimization at this step where we throw away free
       ranges that are less than a certain size.  The logic is that, for
       a couple of reasons, it is better to include a little bit of free
       data in the image if it allows for a single larger contiguous
       allocated range.
     * The list is then inverted to get the "allocated" block list.
       This we traverse in order to read the disk, compress, and make
       the image.

   So the most important operation is insert, and it isn't necessary to
   maintain a sorted list.  However, it might prove to be practical to
   keep it sorted if merge operations can be efficiently performed.  An
   alternative approach, to avoid the invert operation, would be to start
   with a single allocated range (blocks 0 - sizeof_disk) and every time
   we "add a free range" we are actually splitting the allocated range.
   In other words, we keep a sorted, allocated block list from the beginning.

   How big of lists do we need to worry about?  It is hard to say,
   realistically, how big a disk is reasonable to image with imagezip.
   Attempting to image my 1TB disk at home yielded O(100,000) free block
   ranges.  Consider our current biggest disk at Emulab which is a 16TB array;
   i.e., over 30 million sectors.  Worst case is that every other sector
   is free, so the list--be it "free" or "allocated"--would be around 15
   million entries.  So, whatever data structure we choose, should probably
   handle O(1,000,000) and probably even 1-2 orders of magnitude larger.

   How efficient does it need to be?  Certainly not N**2 in the number of
   list entries as it is now!  Consider the 16TB array case above, and note
   that saving such an image, with 8TB of valid data--even assuming say 10-1
   compression and 250MB/sec sustained IO throughput--would take around an
   hour.  Having it take 1-5 minutes for list management would be acceptable.

   Note 1: there is also a "reloc" list, which identifies ranges of
   allocated blocks for which relocations must be performed in order to
   keep imagezip data "position independent" so that, e.g., a Linux partition
   image can be laid down anywhere on a disk.  However, relocations are
   infrequent enough that we don't necessarily have to optimize this list.

   Note 2: back in ye ole OSKIT days, we created an "address map manager"
   library which could apply here:
   http://www.cs.utah.edu/flux/oskit/html/oskit-wwwch26.html#x40-213400026
   but that was still implemented with singly-linked lists.

12. Better handling of "insignificant" free ranges.
   [ DONE: via the fixup method mentioned and a new -Z option. ]
   The -F option in imagezip let's you say that free ranges below a
   certain size should be "forgotten", effectively making that range
   allocated. This promotes longer sequential writes at the expense of
   some garbage data in the image. It also reduces the total number of
   ranges in an image, but that is secondary. This option can make a
   HUGE difference to imageunzip by reducing the number of seeks, so
   this is a really worthwhile option. Two mutually exclusive tasks
   related to -F:

   One is to make sure that any free blocks included in the image as a result
   of -F are zeroed. Since we cannot know if the consumer of the image is
   going to want to zero free space (imageunzip -z) we have to assume they
   will. This will also reduce the size impact of including free blocks in
   the image. I think this can be done easily using a fixup function in
   imagezip. Note that this change ties in with #10 above, if we do that one,
   we would just mark -F identified blocks as zero-ranges.

   Alternatively, we eliminate -F entirely and let imageunzip handle it.
   This is more complex. When processing a chunk, imageunzip would look
   at the free space between consecutive ranges (say, A and B) and determine
   if that range of free space (C) should be "ignored." If so, it would
   allocate a buffer of length A+C+B and zero out the middle part before
   decompressing into the A and B parts. Or, if we were to do #13 below,
   we would instead just add a "write-zero" writebuf describing the free
   range to the queue and the DiskWriter would do a gather-style write
   of A, C, and B.

13. Re-order writes in the DiskWriter.
   Right now we just have a FIFO queue which the disk writer thread
   slavishly processes in order. We could allow the writer (or the
   decompresser that queues writs) to re-order the queue with an elevator
   algorithm or some such. More importantly, it could combine consecutive
   requests so that we could use "writev" to do them all in one operation.
   One could argue that the queue is often not long enough for this to help,
   and that is true. But in those cases the disk is clearly fast enough to
   keep up and it doesn't need any help! So it will benefit the cases that
   matter.

14. Support for TRIM.
   Both FreeBSD and Linux have block-level support for erase operations
   that use the TRIM interface on SSDs. Imagezip and imageunzip/frisbee
   could use this. For imagezip, this would involve ensuring that free
   ranges are in erase-sized (256K) pieces and appropriately aligned
   where possible. This would allow imageunzip to inform the OS when it
   encounters an aligned, appropriate-sized free range that can be erased.
   Hmm...though it appears that FreeBSD doesn't export an "erase" command
   to user-mode, only to filesystems. Linux does, at least "hdparm" supports
   "--trim-sector-ranges" which uses it to erase sections of a disk.

15. Better filling of chunks.
   Look at public-domain fitblk.c as a way to better fill the 1MB chunks
   rather than our ad-hoc "give it smaller and smaller pieces the closer
   we get to 1MB". Ours is more time efficient (single pass), but fitbit
   will probably do a better job of compressing data into chunks (but
   make three compression passes!) Note that our input granularity is
   sectors (or possibly 64K hash-block sized pieces) rather than bytes so
   it makes the input part a little more complicated.

16. Better tools for delta images.
   There are lots of opportunities for "off-line" manipulation of delta
   images; e.g., creating full images from deltas or vice-versa.
   See TODO.tools.
