Did you mean to reply to the list? I'm taking the liberty of sending
my reply to the list.
On 2005-07-06 17:50:07 -0400 Horst von Brand <[email protected]>
wrote:
Hubert Chan <[email protected]> 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.
Which space are you talking about? Disk space, or memory space?
Anyways, for disk space, you're basically just doubling the size of
the tree -- two pointers per link instead of one.
As for memory space, the DFS only takes a couple of words times the
depth of the tree.
People (that I know of) don't normally have a huge lot of hardlinks
to a
single file.
Can't rely on that...
And then there is the (very minor) problem is that meanwhile
/nothing/
can touch the filesystem to do any change...
If the DFS is quick, it shouldn't make much difference.
Lock nodes as you walk up the tree, and people can change unlocked
nodes
without harming anything. All you need to do is make sure that no up
pointers get added to nodes that you've already looked at.
If somebody meanwhile tries to link an ancestor of (one of) your
node(s) to
a descendent, you've got two DFSes going at once through the same
paths...
a single lock won't help.
Good point. You would need to use a counter instead of just a flag
for the lock.
There's another problem with my proposal though (finding it is left as
an exercise for the reader ;-) ). I think it can be avoided, but I
don't have the time right now to properly write it up. (No time to
properly write out what the problem is either. I'm already behind on
my work as it is!) Maybe next week... (Out of town this weekend.)
Anyways, you only really need to prevent creating other hard links
while doing the DFS. Unliking won't cause a problem -- worst that can
happen is that the DFS gives you a false positive. (OK, you need to
make sure that the new parent that you're linking the child node to
doesn't disappear from under you.) Creating new files/directories
won't case a problem -- they're new files/directories; they can't
cause cycles.
Besides, you lost the nice property of top-down lock ordering that
makes
the traversal of Unix filesystems naturally deadlock-free.
Yes, I don't know much about what locks the filesystem/VFS does
already. I'll need to look into that.
--
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]
| |
 |