From mboxrd@z Thu Jan 1 00:00:00 1970 From: Valerie Henson Subject: Re: [RFC] TileFS - a proposal for scalable integrity checking Date: Wed, 9 May 2007 12:01:13 -0700 Message-ID: <20070509190112.GC18778@nifty> References: <20070428220522.GN11166@waste.org> <20070429232349.GA19937@thunk.org> <20070430014042.GL11115@waste.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Cc: Theodore Tso , linux-fsdevel@vger.kernel.org To: Matt Mackall Return-path: Received: from mga06.intel.com ([134.134.136.21]:51034 "EHLO orsmga101.jf.intel.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1755373AbXEITBB (ORCPT ); Wed, 9 May 2007 15:01:01 -0400 Content-Disposition: inline In-Reply-To: <20070430014042.GL11115@waste.org> Sender: linux-fsdevel-owner@vger.kernel.org List-Id: linux-fsdevel.vger.kernel.org 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