Greetings, filesystem algorithm fans.
The recent, detailed description of the versioned pointer method for

volume versioning is here:
   http://linux.derkeiler.com/Mailing-Lists/Kernel/2008-07/msg02663.html
I apologize humbly for the typo in the first sentence.  Today's revision

of the proof of concept code is cleaned up to remove some redundant

logic from the exception delete and origin write algorithms, and has

a number of small improvements.  The fuzzing test has run to 20 million

iterations without problems.  Some of the more complex logic has become

simple to the point where it can possibly be seen to be correct in

addition to merely running correctly.
The current efficiency scores for the six basic operations are:
   Origin write:         O(exceptions)

   Snapshot write:       O(versions)

   Snapshot delete:      O(versions)

   Snapshot read:        O(exceptions)

   Snapshot of origin:   O(versions)

   Snapshot of snapshot: O(versions)
This is mainly about CPU time rather than filesystem efficiency.  The

real time performance will be dominated by disk operations as usual.
Snapshot write is a frequent operation and snapshot delete is performed

on large amounts of metadata at a time, so it would be nice to improve

their performance to be independent of the number of versions created.
O(exceptions) orphan test

-------------------------
It is only the orphan searches that increase snapshot write and

snapshot delete running times from O(exceptions) to O(versions),

otherwise the main algorithm is already O(exceptions).
The orphan test is used in snapshot write and exception delete to

identify any new orphans created as a result of a write that creates an

exclusive exception for the only heir of the ghost exception, or a

delete that removes the only heir and does not promote a new heir.
The current method of determining whether a ghost exception is an

orphan is to recurse through the subtree below the ghost until a visible

version is found that inherits the e...
[ message continues ]