Re: reiser4 plugins

[David Masover <ninja@slaphack.com>]

Hubert Chan wrote:
> On Wed, 06 Jul 2005 16:33:23 -0400, Horst von Brand <vonbrand@inf.utfsm.cl> said:
>
>
> > Hubert Chan <hubert@uhoreg.ca> wrote:
> >
> > > 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.
>
>
> People (that I know of) don't normally have a huge lot of hardlinks to a
> single file.

And speaking of which, the only doomsday scenario (running out of RAM) 
that I can think of with this scheme is if we have a ton of hardlinks to 
the same file and we try to move one of them.  But this scales linearly 
with the number of hardlinks, I think.  Maybe not quite, but certainly 
not exponentially.

The only other doomsday scenario is if we have a ludicrously deep tree.

To make this work in real usage, not DOS testing, we really need both of 
those, and even then I'm not sure it can work.  What's the maximum 
number of hardlinks supported to a single file?  What's the maximum tree 
depth?  Can these be limited to prevent actual DOS attempts?

Now, if we were to ever actually *create* a cycle, then yes, we might 
end up traversing the whole tree to delete it, possibly running out of 
RAM.  But we don't ever actually create cycles except if we were to have 
corruption, which could as easily create cycles in any other FS.
-
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/