Re: reiser4 plugins

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

 



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".

[1] BTW, I had also previously looked at online/dynamic algorithms, for
those who are familiar with that area.  The best known so far is still
O(n) worst case, but much, much smaller in "most cases".

-- 
Hubert Chan <[email protected]> - http://www.uhoreg.ca/
PGP/GnuPG key: 1024D/124B61FA
Fingerprint: 96C5 012F 5F74 A5F7 1FF7  5291 AF29 C719 124B 61FA
Key available at wwwkeys.pgp.net.   Encrypted e-mail preferred.

-
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