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 - To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
