Hubert Chan wrote:
On Wed, 06 Jul 2005 23:42:50 -0700, Hans Reiser <[email protected]> said:
Oh no, don't store the whole path, store just the parent list. This
will make fsck more robust in the event that the directory gets
clobbered by hardware error.
I don't think it affects the cost of detecting cycles though, I think
it only makes fsck more robust.
It doesn't affect the worst-case cost of detecting cycles; by necessity,
any (static [1]) directed cycle detection algorithm must take O(n) time,
n being the size of the tree (nodes + links). However, under
"reasonable assumptions" (where the reasonableness of those assumptions
may be questioned, but I think they're reasonable), I think that doing a
depth-first-search through the parent links makes the algorithm
not-too-terrible. Namely, the "reasonable assumptions" are that a node
doesn't have "too many" parents, and the filesystem hierarchy is not
"too deep".
And, remember, there are other things affected by depth of the tree
anyway. For that matter, most of the time, when you push a system past
"reasonable assumptions", you hit performance issues, if not stability
ones. Most everything but Reiser assumes that you won't have "too many"
files in a directory, or "too many" small files in the FS as a whole.
I think it's fair to assume people will keep things "reasonable",
especially if we tell them what "reasonable" means. As in, "This is the
kind of organization which Reiser4 handles really well, and this is the
kind of organization which will absolutely kill your performance."
-
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]
| |
 |