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

[Matt Mackall <mpm@selenic.com>]

On Wed, May 09, 2007 at 12:01:13PM -0700, Valerie Henson wrote:
> 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?

It should be pretty straightforward as mods to filesystems go. Most of
the work is in shimming the tile read/write layer under the rest of
the FS with helper functions and teaching the file I/O code to pass
down the reverse pointers to the tile layer.

Truncate/rm will also have to null out reverse references on tiles,
but that can be done at the same time bits are fixed up in the block
bitmaps.

Fixing up directories to record the hardlink ring should be easier.

-- 
Mathematics is the supreme nostalgia of our time.