HAMMER 38E/Many: Undo/Synchronization and crash recovery

* Fix a couple of deadlocks.

* Fix a kernel buffer cache exhaustion issue.

* Get the 'hammer prune' and 'hammer reblock' command working ag

HAMMER 38E/Many: Undo/Synchronization and crash recovery

* Fix a couple of deadlocks.

* Fix a kernel buffer cache exhaustion issue.

* Get the 'hammer prune' and 'hammer reblock' command working again. The
commands are now properly synchronized for crash recovery.

show more ...

HAMMER 38D/Many: Undo/Synchronization and crash recovery

* The flusher now waits for I/O to complete at the appropriate points.

* Implement instant crash recovery. The UNDO FIFO is scanned backwar

HAMMER 38D/Many: Undo/Synchronization and crash recovery

* The flusher now waits for I/O to complete at the appropriate points.

* Implement instant crash recovery. The UNDO FIFO is scanned backwards
and reapplied to the filesystem on mount. There is still more work
to do here, inode<->inode associations (e.g. directory entry vs file)
are not yet bound together.

* Clean up I/O sequencing a lot and get rid of a ton of unnecessary flusher
wakeups.

show more ...

HAMMER 38C/Many: Undo/Synchronization and crash recovery

* Classify buffers as meta, undo, or data buffers, and collect them
into separate lists so they can be flushed in the proper order.

* Make

HAMMER 38C/Many: Undo/Synchronization and crash recovery

* Classify buffers as meta, undo, or data buffers, and collect them
into separate lists so they can be flushed in the proper order.

* Make the META buffers and volume header flushed under HAMMERs direct
control only, as part of the UNDO sequencing.

* Major work on the flusher thread. Flush the various buffer classes in
the correct order (the synchronization points are not yet coded, however).

* Update the volume header's UNDO fifo indices.

* Add a ton of sanity checks on buffer modifications and narrow the size
of some of the UNDO records.

* Clean-up after loose IOs. An IO can be loose when its ref count drops
to zero and the kernel attempts to reclaim its bp. We can't garbage
collect the IO in the kernel bioops callback so we have to remember
that the IO is now loose and do it later (in the flusher).

* Temporarily comment out an allocator iterator feature which we cannot
do right now because it may result in new data allocations overwriting
old deletions which are still subject to UNDO.

show more ...

HAMMER 38A/Many: Undo/Synchronization and crash recovery

* Separate all frontend operations from all backend media synchronization.
The frontend VNOPs make all changes in-memory and in the fronten

HAMMER 38A/Many: Undo/Synchronization and crash recovery

* Separate all frontend operations from all backend media synchronization.
The frontend VNOPs make all changes in-memory and in the frontend
buffer cache. The backend buffer cache used to manage meta-data is
not touched.

- In-memory inode contains two copies of critical meta-data structures
- In-memory record tree distinguishes between records undergoing
synchronization and records not undergoing synchronization.
- Frontend buffer cache buffers are tracked to determine which ones
to synchronize and which ones not to.
- Deletions are cached in-memory. Any number of file truncations
simply caches the lowest truncation offset and on-media records
beyond that point are ignored. Record deletions are cached as
a negative entry in the in-memory record tree until the backend
can execute the operation on the media.
- Frontend operations continue to have full, direct read access to
the media.

* Backend synchronization to the disk media is able to take place
simultaniously with frontend operations on the same inodes. This
will need some tuning but it basically works.

* In-memory records are no longer removed from the B-Tree when deleted.
They are marked for deletion and removed when the last reference goes
away.

* An Inode whos last reference is being released is handed over to the
backend flusher for its final disposition.

* There are some bad hacks and debugging tests in this commit. In particular
when the backend needs to do a truncation it special-cases any
negative entries it finds in the in-memory record tree. Also, if a
rename operation hits a deadlock it currently breaks atomicy.

* The transaction API has been simplified. The frontend no longer allocates
transaction ids. Instead the backend does a full flush with a single
transaction id (since that is the granularity the crash recovery code will
have anyway).

show more ...

HAMMER 37/Many: Add a flush helper thread, clean up some inconsistencies.

This patch generally cleans up transaction id inconsistencies betwen data
and meta-data by syncing the data and inode in a s

HAMMER 37/Many: Add a flush helper thread, clean up some inconsistencies.

This patch generally cleans up transaction id inconsistencies betwen data
and meta-data by syncing the data and inode in a single transaction.

* Change the I/O path for write strategy calls. Queue the BIO's to the
flush helper thread instead of directly updating the media.

* We no longer try to sync individual buffers. If the kernel wants to
sync a dirty buffer, we sync the whole file to minimize inode updates.

show more ...

HAMMER 35/many: Stabilization pass, cleanups

* Fix a buffer load race which could result in an assertion or panic
related to a referenced HAMMER buffer with a NULL bp. The problem was
that the

HAMMER 35/many: Stabilization pass, cleanups

* Fix a buffer load race which could result in an assertion or panic
related to a referenced HAMMER buffer with a NULL bp. The problem was
that the loading flag must be used when releasing the buffer as well
as when acquiring the buffer. Change the loading flag to a loading
count.

* Do not lose flush requests. The flush request now stays flagged until
the buffer is able to be flushed.

* Fix stale blockmap offsets cached in hammer_buffer. Clear the cached
offset when freeing a big block from the blockmap. NOTE: We do not yet
try to index buffers based on the blockmap offset but we should.

* Remove the old write ordering code in preparation for redoing the algorithm.

* General code cleanups.

show more ...

HAMMER 33/many: Expand transaction processing, fix bug in B-Tree

* Expand transaction processing to cover more of the code space for
upcoming undo code.

* Fix a bug in the btree_split_leaf(), the

HAMMER 33/many: Expand transaction processing, fix bug in B-Tree

* Expand transaction processing to cover more of the code space for
upcoming undo code.

* Fix a bug in the btree_split_leaf(), the separator would sometimes not
properly be to the left of the split point, resulting in a panic.
Temporarily add many more assertions to btree_split_leaf().

* Improve the critical path for blockmap lookups, the (newly) passed trans
already contains a referenced root volume so the blockmap code does not
have to acquire one.

Reported-by: YONETANI Tomokazu <qhwt+dfly@les.ath.cx> (B-Tree bug)

show more ...

HAMMER 28A/many: Translation and write performance optimizations

* Cache a buffer's virtual (zoneX->zone2) translation to avoid unnecessary
re-translations when a hot-cached buffer is available.

HAMMER 28A/many: Translation and write performance optimizations

* Cache a buffer's virtual (zoneX->zone2) translation to avoid unnecessary
re-translations when a hot-cached buffer is available.

* Use the sequential heuristic provided by the kernel to detect sequential
writes and call bawrite() instead bdwrite() in such cases. This
prevents the buffer cache from hitting slow fallback cases and
completely solves the write performance issue.

Note that the undo fifo is not yet in place and performance will drop
slightly once it is, but what you see now is basically what you're gonna
get in the final.

* Performance is now on par with UFS.

show more ...

HAMMER 27/many: Major surgery - change allocation model

After getting stuck on the recovery code and highly unoptimal write
performance issues, remove the super-cluster/cluster and radix tree bitmap

HAMMER 27/many: Major surgery - change allocation model

After getting stuck on the recovery code and highly unoptimal write
performance issues, remove the super-cluster/cluster and radix tree bitmap
infrastructure and replace it with a circular FIFO.

* Nothing is localized yet with this major surgery commit, which means
radix nodes, hammer records, file data, and undo fifo elements are
all being written to a single fifo. These elements will soon get their
own abstracted fifos (and in particular, the undo elements will get a
fixed-sized circular fifo and be considered temporary data).

* No sequence numbers or transaction spaces are generated yet.

* Create a 'hammer_off_t' type (64 bits). This type reserves 4 bits for
a zone. Zones which encode volume numbers reserve another 8 bits,
giving us a 52 bit byte offset able to represent up to 4096 TB per
volume. Zones which do not encode volume numbers have 60 bits available
for an abstracted offset, resulting in a maximum filesystem size of
2^60 bytes (1 MTB). Up to 15 zones can be encoded.

As of this commit only 2 zones are implemented to wrap up existing
functionality.

* Adjust the B-Tree to use full 64 bit hammer offsets. Have one global B-Tree
for the entire filesystem. The tree is no longer per-cluster.

* Scrap the recovery and spike code. Scrap the cluster and super-cluster
code. Scrap those portions of the B-Tree code that dealt with spikes.
Scrap those portions of the IO subsystem that dealt with marking a
cluster open or closed.

* Expand the hammer_modify_*() functions to include a data range and add
UNDO record generation. Do not implement buffer ordering dependancies
yet (ordering issues are going change radically with the FIFO model).

show more ...

HAMMER 25/many: get fsx (filesystem test) working, cleanup pass

* Fix buffer alignment in the write strategy code. Assert buffer alignment
in hammer_ip_sync_data().

* Finish implementing file tr

HAMMER 25/many: get fsx (filesystem test) working, cleanup pass

* Fix buffer alignment in the write strategy code. Assert buffer alignment
in hammer_ip_sync_data().

* Finish implementing file truncation. There's probably still an edge case
or two related to B_CACHE on terminal filesystem buffers when expanding
a file.

* Pass VCHR vnodes through to fsync so the inode data syncs properly. It
was previously only syncing on umount or OS flushes.

* Change a bunch of debugging kprintf's to only print if a debug variable is
set. Reduce the debugging output considerably.

* Test FSX using both a full historical mount and a nohistory mount.

show more ...

HAMMER 24/many: Clean up edge cases

Hammer now survives many cpdup/rm-rf loops with recovery forced on.

* Fix an edge case with historical lookups. When pushing down through a
spike an exact mat

HAMMER 24/many: Clean up edge cases

Hammer now survives many cpdup/rm-rf loops with recovery forced on.

* Fix an edge case with historical lookups. When pushing down through a
spike an exact match on a SPIKE_END element is no guarantee of success,
so check for and flag the delete boundary in that case.

* Delay physical cluster deletions (marking the cluster as free in the
Volume's A-list) until the last ref on the cluster goes away.

* Fix a race between cluster deletion, filesystem sync, and recovery.
Do not attempt to recover a cluster marked as undergoing deletion.

* Enable cluster recovery by default. It is still fairly primitive but
it should work well enough to put the filesystem in a working state
once the remaining debug shims are removed.

* Clean up sequencing of io->modified to ensure that clusters are properly
closed during normal operation. Recovery operations should only occur
when encountering an open cluster after a crash.

* Do not open a cluster or create a cluster->buffer dependancy when only
updating the mtime or atime of an inode.

* In the hammer_sync_*() procedures, ref the volume/cluster prior to
scanning its RB tree, use hammer_ref() instead of hammer_ref_*() to
avoid unnecessary loads. This also fixes a stale pointer bug in the
same code.

* Remove the stack recursion in btree_remove(). btree_remove() is now able
to clean up empty nodes going all the way up the tree (at least until it
hits a deadlock, which is not yet handled).

* Fix primary filesystem statistics (they were getting off because
whole clusters were being deleted without bothering to free up internal
on-disk structures).

* Fix a minor bug in the cluster's stat_records tracking field. 'df' no
longer shows a bleeding capacity. Statistics will still get off due
to crashes and such (the balancer will probably have to deal with that).

* Add more assertions. How do you debug complex code? You assert that
everything is in its proper state, everywhere you can.

show more ...

HAMMER 23/many: Recovery, B-Tree, spike, I/O work.

Warning: filesystem structures have changed, recompile newfs_hammer too.

* Correct a couple more edge cases with historical lookups. We have to

HAMMER 23/many: Recovery, B-Tree, spike, I/O work.

Warning: filesystem structures have changed, recompile newfs_hammer too.

* Correct a couple more edge cases with historical lookups. We have to
flag the need for an iteration anywhere the edge case is hit as we
recurse down, not just on the terminal B-Tree node.

* Get rid of the kludge record buffer bitmap in the cluster header. Augment
the A-List recovery and scanning code to locate record buffers. This
required adding some unfortunate complexity to the A-list search and
recovery routines due to the fact that we ran out of bit codes and
couldn't represent an all-free/initialized AND an all-free/uninitialized
case.

* Go back to making the SPIKE_END elements range-inclusive instead of
range-exclusive. It turns out that making them range-exclusive caused
a few too many collisions with adjacent records in the B-Tree.

* Excellent progress on the recovery code. It still has numerous issues
(there are lots of recovery cases I still have to implement), but
it survives much longer now. Add a sysctl to disable/enable/force
cluster recovery (default disabled, since its still buggy).

* When creating a spike be sure to properly assign the cluster record's
rec_offset.

* When removing a spike be sure to also free the related cluster record.

* Spike code progress. Implement the last case it couldn't handle (spiking
a spike) and add a very simple starter heuristic which generates a
better spike topology (doesn't create long chains of end-range spikes).

* Add a huge number of new assertions to ease the tracking down of bugs.

* Address some IO sequencing issues that could result in io.modified
getting prematurely cleared. io.modified can only be cleared on write
initiation on the last ref to a HAMMER structure.

* Add a hack to pre-reserve enough B-Tree buffers to guarantee the recovery
code can regenerate the B-Tree without having to pack it. This ultimately
needs to be fixed (the recovery code really needs to pack the tree).

show more ...

HAMMER 18B/many: Stabilization pass

* Fix B_LOCKED buffer leakages by clearing B_LOCKED when a bp is
disassociated from its related HAMMER structure.

* The sync code can be called with a buffer s

HAMMER 18B/many: Stabilization pass

* Fix B_LOCKED buffer leakages by clearing B_LOCKED when a bp is
disassociated from its related HAMMER structure.

* The sync code can be called with a buffer still referenced from
other sources, so hammer_flush_buffer_nodes() can't be called. The
refactored hammer_node abstraction no longer holds active refs on
the underlying buffer anyway (unless actively referenced itself), so
there is no need to flush it to guarentee that the buffer itself gets
flushed.

show more ...

HAMMER 18/many: Stabilization pass

* Properly flag the inode when dirty buffer cache buffers are present so
fsync syncs them. Fixes a umount panic.

* Fix A-list bugs introduced when I added the

HAMMER 18/many: Stabilization pass

* Properly flag the inode when dirty buffer cache buffers are present so
fsync syncs them. Fixes a umount panic.

* Fix A-list bugs introduced when I added the '10' bit code to record
an all-allocated/initialized state vs '00' (all-allocated uninitialized).

* Fix an A-list bug in *alloc_rev. A comparison was off and could result
in a near full A-list from incorrectly believing it was completely full.

* When generating a spike also allocate a spike record for the recovery code
to find.

* Generate the initial free blocks for a hammer buffer via its cluster A-list
instead of directly so the cluster A-list's meta-data is properly
synchronized.

show more ...

HAMMER 17/many: Refactor IO backend, clean up buffer cache deadlocks.

Rewrite HAMMER's IO backend, sans locking which will occur in another patch.
The new backend is far less confusing though I woul

HAMMER 17/many: Refactor IO backend, clean up buffer cache deadlocks.

Rewrite HAMMER's IO backend, sans locking which will occur in another patch.
The new backend is far less confusing though I wouldn't exactly call it
simple.

The new backend keeps track of dependancies with a structure->structure
dependancy list, plus implements the special case of opening and closing
a cluster header. Buffers are synchronized first, then cluster headers,
then volume headers. The new backend also removes a number of potential
deadlocks.

show more ...

HAMMER 16/many - Recovery infrastructure, misc bug fixes

* Add A-list recovery and iteration support. This code fixes up an A-list
which might have been partially modified or gotten out of sync.

HAMMER 16/many - Recovery infrastructure, misc bug fixes

* Add A-list recovery and iteration support. This code fixes up an A-list
which might have been partially modified or gotten out of sync.

* Add substantial cluster recovery infrastructure (not yet enabled). The
code still needs to go through a few test/debug cycles and does not
yet handle cluster pushes.

* Fix a critical section and a bug in the A-list empty-check code (the
latter not yet used by HAMMER but will be soon). The wrong base free
block count was being supplied.

* Add a synchronizing transaction id field to the cluster header. This
field will be used by the recovery code.

* For the moment add a bitmap of buffers allocated to record arrays. The
bitmap is in the cluster header. This may or may not be temporary. For
now it will allow the recovery code to wipe the cluster's A-list's and
then iterate records to regenerate them.

show more ...

HAMMER 15/many - user utility infrastructure, refactor alists, misc

* Abstract out userland access to HAMMER's on-disk structures in
preparation for more userland work.

* Clean up compiler warnin

HAMMER 15/many - user utility infrastructure, refactor alists, misc

* Abstract out userland access to HAMMER's on-disk structures in
preparation for more userland work.

* Clean up compiler warnings.

* Refactor the A-list recursion API. Use another bit code (10) to indicate
the all-allocated & initialized state, verses an all-allocated &
uninitialized state.

This allows an all-empty flag to propogate up the chain properly which
in turn allows us to avoid flushing out dirty backing store for freed
disk blocks and will eventually lead to freeing typed buffers back to
the cluster's master a-list.

* Fix an edge case in the B-Tree code related to running out of space
during an insertion search. If the insertion search ran out of space
at a cluster boundary the spike code asserted because the parent B-Tree
node wasn't in the same cluster as the node it thought it had to spike.
(The root B-Tree node of a cluster cannot be spiked).

* Use a second cache pointer in the in-memory structure for directory
inodes. The second cache will be used for inode lookups relative to
the directory and will (eventually) greatly reduce the B-Tree search
overhead required to stat directory elements.

show more ...

HAMMER 14/many - historical access cleanup, itimes, bug fixes.

With this commit most historical accesses work and I can go through at least
two cycles of cpdup / rm -rf without crashing.

* Fix a bu

HAMMER 14/many - historical access cleanup, itimes, bug fixes.

With this commit most historical accesses work and I can go through at least
two cycles of cpdup / rm -rf without crashing.

* Fix a bug in the B-Tree code related to searches on historical records.
These records are differentiated by key.create_tid but unlike the rest
of the key the matching algorithm has to be somewhat more sophisticated.
e.g. A search as of time 10 needs to find a record with a create_tid of 5.

To make this work properly we use a trick when we generate the separator
when splitting a leaf. see hammer_btree.c / hammer_make_separator().

* Recycle inodes a link count of 0 immediately.

* Optimization: Do not flush backing store to disk on reclaim.

* Add a per-inode read-only flag. Mark all historical inodes as read-only

* Implement read-only semantics in the vnops and assert attempts to modify
inodes marked read-only.

* Properly record the last transaction id for use when synchronizing
inodes to the platter. There were a few cases when late synchronizations
were using the wrong transaction id, breaking user expectations when
accessing historical data after a sync.

* Update the itimes (atime and mtime). These are non-historical updates by
default (meaning we just overwrite the latest inode record instead of
deleting it and inserting a new one). A future mount option will allow
these updates to operate historically (the coding is trivial)... didn't
you always want to know the last time a file was accessed prior to a
particular date? Think about it...

* Fix an inode memory leak. The inode in-memory structure must be freed
on last reference. There were cases where it was being left in the
HAMMER cache.

* Optimization: Reduce vnode scan overhead during 'sync' by improving
on the inode flags which indicate that some sort of sync is required.

* Optimization: Don't flush inodes when their link count drops by 1, try
to only flush them when their link drops to 0.

* Fix a couple of potential deadlocks.

* Fix a case in the vnops code where an inode was not being properly flagged
as being dirty.

show more ...

HAMMER 13/many - Stabilization commit

* Clean up the in-memory record API.

* Add B-Tree boundary assertions and B-Tree debugging code.

* Delay freeing bits in the allocation bitmaps for B-Tree nod

HAMMER 13/many - Stabilization commit

* Clean up the in-memory record API.

* Add B-Tree boundary assertions and B-Tree debugging code.

* Delay freeing bits in the allocation bitmaps for B-Tree nodes and
clusters until the last reference to the in-memory structure goes away.
This avoids premature reallocation.

* Fix a bug in btree_split_leaf() - the cursor was not being properly
adjusted in a particular boundary case.

* Fix a recursive lock bug on a buffer cache buffer in hammer_io.c

* Do not allow a non-empty directory to be removed.

* Synthesize directory entries for "." and "..". Adjust the
hammer_directory_namekey() procedure to reserve key-space for the
synthesized entries.

* Fix memory leaks related to the hammer_node and hammer_record structures.

* Finish writing the rename code.

show more ...

HAMMER 12/many - buffer cache sync, buffer cache interactions, misc fixes.

As of this commit all vnops work, the filesystem remains consistent across
umount/remount, and the 'cpdup / /mnt/root' test

HAMMER 12/many - buffer cache sync, buffer cache interactions, misc fixes.

As of this commit all vnops work, the filesystem remains consistent across
umount/remount, and the 'cpdup / /mnt/root' test succeeds. There is still
a ton of work to do but this is a major milestone.

* Get sync and umount working properly. Properly sync out in-memory records
and inode updates, and properly release buffer cache buffers so the
kernel can throw them away.

* Modifications to buffers backed by the buffer cache ensure that any
asynchronous writes complete to avoid a modify-write race.

* Fix miscellanious reference counting bugs.

* Fix two insertion bugs for internal B-Tree nodes that were causing the
code to blow up.

show more ...

HAMMER 12/many - add VOPs for symlinks, device, and fifo support.

* Add some missing VOP bits. Add a fixed attribute record type and store
the symlink path as fixed attribute record #1.

* Adjust

HAMMER 12/many - add VOPs for symlinks, device, and fifo support.

* Add some missing VOP bits. Add a fixed attribute record type and store
the symlink path as fixed attribute record #1.

* Adjust hammer_inode_data to add missing major and minor device fields.

* Add support for adding generic records and special case deletion of
an object's entire set of records.

* Fix a minor bug that was causing the root cluster to be improperly kfree()'d.

show more ...

HAMMER 11/many - initial spike commit.

* Fix a bug in the cluster disk offset calculation.
* Implement the cluster allocator and related header initialization.
* Remove wildcarding from hammer_btree

HAMMER 11/many - initial spike commit.

* Fix a bug in the cluster disk offset calculation.
* Implement the cluster allocator and related header initialization.
* Remove wildcarding from hammer_btree_cmp().
* Move the historical filter out of hammer_btree_cmp() and into its own
procedure.
* Allow the ending element in a B-Tree range iteration to be inclusive or
exclusive of the range.
* Add infrastructure for cluster-localizes searches.
* Initial commit of the spike code (still in progress).

This commit brings in most of the infrastructure needed for the spike code.
The spike code is what glues one cluster's B-Tree to another cluster's B-Tree.
At the moment we spike by taking the B-Tree leaf node at the cursor after
a search and moving all of its elements to a new cluster, then replacing
the pointer to that leaf node in the parent B-Tree node with a cluster
reference.

This is non-optimal at the moment. Several optimizations are possible and
will be eventually be implemented.

show more ...

HAMMER 10/many - synchronize miscellaneous work.

* Cleanup the I/O infrastructure a bit in preparation for a write interlock.
* Fix a bug in the B-Tree code.
* Implement the cluster open flag and wr

HAMMER 10/many - synchronize miscellaneous work.

* Cleanup the I/O infrastructure a bit in preparation for a write interlock.
* Fix a bug in the B-Tree code.
* Implement the cluster open flag and write dependancies in preparation
for the cluster recovery code.
* Start working on statistics for statfs.

show more ...

HAMMER 8/many - A-list, B-Tree fixes. As-of queries

Fix numerous bugs in the A-list and B-Tree code, and a few other
calculations. The maximum volume size had to be reduced to 8192 TB due
to an ov

HAMMER 8/many - A-list, B-Tree fixes. As-of queries

Fix numerous bugs in the A-list and B-Tree code, and a few other
calculations. The maximum volume size had to be reduced to 8192 TB due
to an overflow in the A-list radix calculation.

Implement as-of name lookups using an @@<delta_seconds_old> name extension.
This is temporary. Implelment as-of mounts.

show more ...

HAMMER 6/many - memory->disk flush, single-cluster sync to disk, more vnops.

Get most operations within a single 64M cluster working. There are still
numerous issues with the B-Tree algorithms so r

HAMMER 6/many - memory->disk flush, single-cluster sync to disk, more vnops.

Get most operations within a single 64M cluster working. There are still
numerous issues with the B-Tree algorithms so readbacks generate bad data at
the moment.

show more ...