Re: reiser4 plugins

[Hubert Chan <hubert@uhoreg.ca>]

On Wed, 06 Jul 2005 12:52:23 -0600, Jonathan Briggs <jbriggs@esoft.com> said:

> On Tue, 2005-07-05 at 23:44 -0700, Hans Reiser wrote:
>> Hubert Chan wrote:
>>> And a question: is it feasible to store, for each
>>> inode, its parent(s), instead of just the hard link count?

>> Ooh, now that is an interesting old idea I haven't considered in 20
>> years.... makes fsck more robust too....

If you can store the parents, then finding cycles (relatively) quickly
is pretty easy: before you try to make A the parent of B, walk up the
parent pointers starting from A.  If you ever reach B, you have a cycle.
If not, you don't have a cycle.  (Hmmm.  Do I need a proof of
correctness for this?  It's just depth-first-search, which everybody
learned in their first algorithms course.)

Running time is (at most) just the sum of all (directed) path lengths
from A to the root.  Assuming people don't have too deep of a hierarchy,
or too much branching with hard links (i.e. nodes with too many
parents), which I think is a reasonable assumption, running time should
be fairly quick.

(People may have millions of files in a single directory, which is why
doing the DFS in the forward direction is a bad idea.  But people
probably don't have millions of hard links to the same file, or
hierarchies that are millions of levels deep.)

And it only happens when a hard link is created -- probably not a very
performance-dependent event (i.e. it's not the scheduling algorithm).  I
would imagine that some creative caching could be done to speed up the
situation where you try to make a whole batch of hard links.  (When you
walk up the parent pointers starting from A, cache the inode numbers
that you encounter.  If you then try to make A the parent of C, check if
C is one of the inode numbers in the cache.  If yes, we have a cycle; if
no, we don't have a cycle.)

Extra disk storage is just about one extra word for most nodes (that
only have one parent -- basically, one extra word per parent), if you
can pack the data efficiently.  (i.e. we don't want to waste a extra
whole block per node.)

Of course, since this requires extra storage on the part of the
filesystem, the (kernel) VFS change would have to be something where the
VFS asks the filesystem whether making A the parent of B will create a
cycle; it's not something the VFS can do transparently for everybody.
Filesystems that don't store this extra stuff just return "yes" if B is
a directory (thus disallowing the link), and "no" if B is a file, and we
get the same situation we have right now.

It would require a disk format change (sort of) in Reiser4, but (as Hans
mentioned) since we have plugins, shouldn't require a reformat (as I
understand it).  Just run a tool that builds the parent-pointer data;
until you run that tool, the filesystem can just disallow hard links.
After you run the tool, updating parent pointers is handled
automatically by the filesystem.

> Hey, sounds like the idea I proposed a couple months ago of storing
> the path names in each file, instead of in directories.  Only better,
> since each path component isn't text but a link instead.

> It still has the performance and locking problem of having to update
> every child file when moving a directory tree to a new parent.  On the
> other hand, maybe the benefit is worth the cost.

Every node should store the inode number(s) for its parent(s).  Not the
path name.  So you don't need to do any updates, since when you move a
tree, inode numbers don't change.

-- 
Hubert Chan <hubert@uhoreg.ca> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/