Convert rangeset implementation from a hashtable to GSequence.

This gives log(N) performance, but allows us to easily tell if a request
falls in the middle of an object and check for overlaps on inserts (though
that part isn't implemented yet).

Implement a rangeset data type and use it to track items in log segments.

The range set can be used to track which byte ranges in a file correspond
to valid objects, and so can be used in the cloud log code to check that
1) objects are actually available if partial log fetching is implemented,
and 2) that objects being fetched have actually been authenticated (if
needed).

This isn't fully working yet.  The range sets should be changed from a hash
table to a sequence, since some lookups in the cloud log code are into the
middle of an object (to skip the header and remap the data), and that needs
to be handled properly.

Add support for byterange requests in the storage layer.

Rename private structures to remove leading underscores.

This is a cosmetic change, but should make debugging and looking up
structure definitions easier.

Merge git+ssh://c09-44.sysnet.ucsd.edu/scratch/bluesky

Updates to the workload generator and some results from runs.

Remove debugging messages when decrypting cloud log segments.

Fix Amazon S3 store_lookup_last implementation.

Amazon will return directory listings in chunks.  Be sure to repeat list
calls until we find the actual end of the directory listing.

Fix a memory leak resulting from the in-memory inode map.

Actually release the reference to the old version of an inode when creating
a new one.

Add a more aggressive mode of cleaning up disk space.

If enough space cannot be deleted in the disk cache, drop nearly all clean
data from memory so that most disk cache files are unreferenced, then make
another pass to delete log/cache files.

Move disk cache cleanup code to cache.c from log.c

A few more minor fixes cleaning up the cloud log state counting.

Fix up cloud log state counting.

Counts of cloud log items in various states were not being kept up to date,
so that the counts were often wrong.  Fix a few cases to make the counts
more accurate.

Ignore lockmem executable.

The signature on log items should not extend to the pointer locations.

This allows the cleaner to rewrite the pointers without invalidating the
signature.

Add timeout on cleaner S3 retry.

Add retries to the S3 backend in the cleaner.

Small utility to use free memory in a system.

For benchmarking, to take memory away from the page cache.

Support encrypted log items in the cleaner.

Delete dead code.

When decrypting a log item also clear out the IV field.

Not really needed, but this way the IV field being zero should be
synonymous with an unencrypted log item.

Add per-item encryption/authentication to the cloud log storage.

We should generate encrypted data and decrypt it again on read, but we
don't yet enforce only reading data which passes the integrity check.

Allow S3 bucket used for BlueSky storage to be specified.

Work on a simple workload generator for benchmarking.

Start adding in selective encryption of cloud log items.

Not fully hooked in, but some of the logic for encryption is written now.

Another logging fix.

Fix for journal committing.

Sometimes we could previously, under load, report that journal items were
committed when they were not.  Try to track the uncommitted state more
carefully now.

Implement handling of unstable data in WRITE/COMMIT nfs procedures.

Before all NFS operations were synchronous; now we support asynchronous
commits of file writes which might improve performance.

Updated microbenchmarking script.

Starting work on scripts to automate benchmarking.

Improve cleaner performance.

When reading an object in, seek to and read just the needed bytes instead
of the entire log segment.  Improves performance significantly.

Remove obsolete file.

Use a thread pool for inode fetches, and remove some debugging output.

Remove an extraneous mutex unlock.

I'm surprised that this didn't cause trouble earlier; it seems that
unlocking an unlocked mutex raises no errors (but under heavy load, when
the mutex is locked by another thread then unlocking it can cause trouble).

More fixes for memory management.

This should allow memory and cache space to be reclaimed by not keeping
items pinned in memory, finally.  Still needs a bit more testing.

Work on reducing memory pinned by the inode map.

Add cleaner option to rewrite and compact all inodes (but not all data).

Allow cloudlog items to be unreferenced in the background.

This is to avoid certain deadlocks, when we don't care if resources are
reclaimed immediately or not.

Do not hold references to all inode data in inode map.

The inode map should not hold full refereces to all inode objects and all
corresponding data, since that will lock all such data in memory or the
disk cache.  Do some initial work towards just holding weak references to
the data so that it can be expired from the cache.

Restart journal sequence numbering properly.

Handle the case even where some old journal files have been deleted.

Add in header fields for per-object encryption/authentication.

These aren't yet used.

Add very basic caching to the cleaner S3 backend.

Add S3 backend for the cleaner.

It does not yet cache files so performance is poor.

Properly set the starting inode number for allocation after restarting.

Fix for S3 list operation.

Implement a list operation for the S3 storage backend.

Drop encryption from the cloud storage backend.

Encryption should properly be provided at another layer, so in preparation
for that remove it from the storage layer.

Allow cleaner to delete unused log segments.

It will not delete segments cleaned out in the current pass, just those
that were unreferenced at the start of the cleaning process.

Improve segment cleaning.

Improve cleaner: make sure new logs are written after existing ones.

Extend cleaner with a simple policy for choosing segments to clean.

Updates to the Python cleaner prototype.

This can now read in the old inode maps, rewrite inode data, and write out
an updated inode map/checkpoint.

Begin work on a segment cleaner prototype.

Right now this can rebuild an inode map and compute segment utilization,
though it isn't very efficient.

Add partial journal replay to filesystem recovery.

After loading a cloud checkpoint, replay just the last portion of the
journal that may not have been committed to the cloud.

Include inode numbers in cloud log items.

Finish up loading of checkpoints from cloud logs.

This is now working, at least with a very minimal test.

In-progress work to implement inode map loading at server start.

This will be used to restore filesystem state from the cloud when the
program starts up again.  It still needs more optimization, needs journal
replay to be run afterwards, and bugfixing.

Improve object deserialization: properly parse object headers.

Start at writing out inode maps to cloud storage.

Fixes for journal replay, and drop the "superblock" cloud item.

That file in the cloud wasn't storing useful information any longer and
wasn't being used much; drop it.  It's functionality will be replaced with
some form of commit log in the cloud journal.

Fix some resource leaks in journal replay.

Implement basic full log replay.

This still needs some checking over for bugs and minor fixes.  It replays
the entire journal from the start to rebuild filesystem state.  Still
needed: partial joural replay, starting from a checkpoint in the cloud.

Update CRC-32 implementation.

Invert the result of the CRC computation at the end.  This will catch extra
null bytes at the end of the buffer, but required updating the CRC
validation.

Add in some support for journal replay.

This isn't all functional yet, but making it fully functional will require
updating the data fields that are written to the journal first...

Start work on log replay for filesystem recovery.

Right now this implements scanning of one journal segment with consistency
checking to find items that were written out.

Also fix the checksum calculation on log entries so that they will validate
properly (we want to compute the checksum so that on validation, computing
the checksum of the entire object results in a value of zero).

Add an inode map data structure to track the location of inodes in logs.

Update logic for flushing data to cloud.

Do not force a commit of the most recent data, and instead just write out
whatever was last written to the journal.

This could be a win or a loss:
  - We do not need to force a sync of all data to the journal when we
    upload data to the cloud.
  - But, we may end up writing out old data, which we'll then need to
    overwrite a short time later.

Make cache size run-time configurable.

Implement new scheme for retaining needed journal segments.

Write full filesystem snapshots to the cloud, and keep track of the journal
position before the snapshot process starts.  When it finishes, the journal
segments before that mark can be reclaimed (if needed).

This could be improved but should at least be safe.

Fix a longstanding(?) memory-leak bug when truncating a file.

Back out dirty reference tracking, as the design was flawed.

Objects can be written to the journal but not to the cloud--for example, if
a data block is written to the journal but overwritten before the file is
flushed to the cloud.  This write-combining is good, but the old code for
tracking when a journal segment could be reclaimed couldn't handle this.

So, back out that dirty reference tracking code, in preparation for
replacing it with another approach.

Make cloud storage more robust.

  - Do not consider data committed until we get a reply from the cloud.
  - Add retries on write and on read.

Add a target size for the cache, and prune the cache when it gets larger.

Track journal files which contain dirty data and which can be reclaimed.

Implement a (dumb) cache garbage collector.

This is a proof of concept; it doesn't delete journal files and deletes
cache files nearly as soon as they are unused, so it needs better
algorithms for choosing when to delete files.  But it does seem to work.

Improve journal/cloud cache locking and add access time tracking.

Debugging/refcount cleanups.

Minor bugfixes/tweaks.

First attempt at supporting reading data back from cloud log segments.

There are still some bugs, hacks, race conditions, etc., but this seems to
be doing mostly the right thing and so is a good start.

Serialized inode data should be dropped from caches, too.

Attempt at limiting the rate at which memory is dirtied.

Reference counting bugfix.

Newly-created inodes should be marked as modified.

The NFS proxy code previously didn't do this, with the result that some
inodes (symlinks were first noticed, but the problem affected other areas
too) would not get entered into the appropriate LRU lists.

More aggressively use memory-mapped data for cloud log items.

Replace a string with a memory-mapped version as soon as possible when the
item is written out.  The intent is that memory-mapped versions rely on the
kernel's memory management, and don't need to be written to swap like a
private copy would, and so should give better overall system memory
management.

Improve tracking of memory usage in BlueSky.

Most data, except for dirty data blocks not flushed out to the journal yet,
will be in the form of cloud log entries.  Create statistics counters to
track how many cloud log items are in each of several states (in memory
only, writeback, on disk, in cloud).

More fixes to BlueSky cache management.

Drop old code for flushing data to the cloud.

Work to unify the cloud segment writing with other cache management.

Split cloud log segments into modestly-sized chunks.

Add a null storage implementation.

This simply discards all data written to it.  Useful for testing purposes,
if all the data remains in the local log and so we never need to fetch data
from the storage implementation.

Fix some memory leaks.

Make links between cloud log entries direct.

Rather than giving the ID provide a direct pointer to the object.

Rework caching of data blocks to eliminate double-caching.

Previously data could be cached both as a cloud log item and as a string at
the inode level.  Now cache as a string for dirty data and a cloud log item
for clean data.

Fix up reference counting for cloud log items.

A few attempted bugfixes for log data lifetimes.

A much better fix will depend on reworking this code a bit more.

Fix up reference counting for memory-mapped journal log segments.

Improve the reading back of objects committed to the journal.

Implement a cache of memory-mapped log files so that when multiple objects
are requested we can re-use the mapping.  Make log files fixed sizes (call
ftruncate when opening the log file) so the entire thing can be memory
mapped at the start.

More cache behavior tweaks.

Preliminary support for dropping cached file data from memory.

Work to allow mmap-ed log entries to be used for data blocks.