Re: reiser4 plugins

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



Hubert Chan wrote:
On Wed, 06 Jul 2005 16:33:23 -0400, Horst von Brand <[email protected]> said:


Hubert Chan <[email protected]> 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 [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[Index of Archives]     [Kernel Newbies]     [Netfilter]     [Bugtraq]     [Photo]     [Gimp]     [Yosemite News]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Video 4 Linux]     [Linux for the blind]
  Powered by Linux