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

["Jörn Engel" <joern@lazybastard.org>]

On Wed, 9 May 2007 14:51:41 -0500, Matt Mackall wrote:
> On Wed, May 09, 2007 at 11:59:23AM -0700, Valerie Henson wrote:
> > 
> > Hrm.  Can you help me understand how you would check i_size then?
> 
> That's pretty straightforward, I think. When we check an inode, we
> have to check whether it has a block that corresponds with i_size, and
> none beyond that.

i_size is indeed simple, but that got me thinking.  i_blocks is a much
harder problem.  Luckily it is almost the same problem as the free/used
block count for the filesystem.  And again the solution would be to have
a tree structure and have a sub-total for each node in the tree.

Now, inodes already have a tree structure, the indirect blocks.  So
indirect blocks would need to get an extra field somewhere to store how
many used blocks are below them somewhere.  Only problem is: indirect
blocks have a nice power-of-two size and no spare space around.

> That begs the question of when we check various pieces of data. It
> seems the best time to check the various elements of an inode is when
> we're checking the tile it lives on. This is when we'd check i_size,
> that link counts made sense and that the ring of hardlinks was
> correct, etc. 

Yup.  Checking i_size costs O(log(n)), i_count with above method is
O(log(n)) as well.  The hardlink ring is O(number of links).  For most
people that don't have a forest of hard-linked kernel trees around, that
should be fairly small as well.

I believe for large files it is important not to check the complete
file.  We can divide&conquer the physical device, so we can do the same
with files.  Although I wonder if that would require a dirty bit for
inodes as well.

> We will, unfortunately, need to be able to check an entire directory
> at once. There's no other efficient way to assure that there are no
> duplicate names in a directory, for instance.

There is.  As long as directories are in htree or similar format, that
is.  Problem is the same as fast lookup.

Jörn

-- 
tglx1 thinks that joern should get a (TM) for "Thinking Is Hard"
-- Thomas Gleixner
-
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html