Re: [RFC] TileFS - a proposal for scalable integrity checking

[Valerie Henson <val_henson@linux.intel.com>]

On Sun, Apr 29, 2007 at 08:40:42PM -0500, Matt Mackall wrote:
> On Sun, Apr 29, 2007 at 07:23:49PM -0400, Theodore Tso wrote:
> > There are a number of filesystem corruptions this algorithm won't
> > catch.  The most obvious is one where the directory tree isn't really
> > a tree, but an cyclic graph.   What if you have something like this:
> > 
> > 				A <----+
> > 			       / \     |
> > 			      B   C    ^
> > 			     /         |
> >   			    D----->----+
> > 
> > That is, what if D's parent is B, and B's parent is A, and A's parent
> > is... D?  Assume for the sake of argument that each inode, A, B, C, D,
> > are in separate tiles.
> 
> From the original message:
> 
>  Inodes have a backpointer to a directory that links them. Hardlinked
>  files have two extra inode pointers in the directory structure, to
>  the previous and next directories containing the link. Hardlinked
>  inodes have a checksum of the members of that list.
> 
> When we check directory D, D's inode has a backpointer (which had
> better match ".." in the directory itself if we keep that
> redundancy!). If we can follow this back to root (using a standard
> two-pointer cycle detection algorith), we have no cycle. As we also
> check that every inode pointed to by directory D also points back to
> D, any deviation from a valid tree can be detected.
> 
> And again, a small cache of inodes known to be properly rooted will
> save a lot of checks.

I really, really like this idea.  I wonder how hard it would be to
prototype on something like ext3.  Any bored grad students listening?

-VAL