Hubert Chan <[EMAIL PROTECTED]> wrote: > 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.) Correct. And you need space for potentially a huge lot of up pointers for each file. And then there is the (very minor) problem is that meanwhile /nothing/ can touch the filesystem to do any change... How do you delete such an object? You will have to delete from each child down to the first object that has a pointer to it from the outside, if you don't want garbage left behind. And that means walking down to /each/ reachable object, then walking up from there to see if all its parents are in the DAG rooted at what you are going to delete. This means potentially walking through the whole filesystem (if you want to delete the root, or something near). You will run out of memory, and again, meanwhile no changes can be allowed. It is for a reason that Unix filesystems don't have up pointers for files, and just leaves (i.e., files) can have multiple hard links. And this /was/ explained in detail the last flamefest over this exact same point. I thought the ReiserFS people had learned from that... -- Dr. Horst H. von Brand User #22616 counter.li.org Departamento de Informatica Fono: +56 32 654431 Universidad Tecnica Federico Santa Maria +56 32 654239 Casilla 110-V, Valparaiso, Chile Fax: +56 32 797513 - 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/
