lkml.org 
[lkml]   [2005]   [Jul]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: reiser4 plugins
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/

\
 
 \ /
  Last update: 2005-07-07 04:47    [W:0.256 / U:3.096 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site