On Wed, 06 Jul 2005 12:52:23 -0600, Jonathan Briggs <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> - 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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
