Skip to contentSkip to conversation

what is necessary for directory hard links

DISCUSSION Bodo Eggert 8 participants 15 messages Jul 22, 2006 – Jul 26, 2006 3 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#2 lore raw
Quoted 5 lines · Horst H. von Brand
Quoted 2 lines · Joshua Hudson

This patch is the sum total of all that I had to change in the kernel VFS layer to support hard links to directories

Can't be done, as it creates the possibility of loops.

Don't do that then?

Quoted 6 lines

The "only files can
be hardlinked" idea makes garbage collection (== deleting of unreachable objects) simple: Just check the number of references.

Detecting unconnected subgraphs uses a /lot/ of memory; and much worse, you have to stop (almost) all filesystem activity while doing it.

In order to disconnect a directory, you'd have to empty it first, and after emptying a directory, it won't be part of a loop. Maybe emtying is the problem ...

This feature was implemented, and I asume it was removed for a reason. Can somebody remember?

Signature · 4 lines
Ich danke GMX dafür, die Verwendung meiner Adressen mittels per SPF
verbreiteten Lügen zu sabotieren.

http://david.woodhou.se/why-not-spf.html
#3 lore raw
Quoted 9 lines · Bodo Eggert
Quoted 5 lines · Horst H. von Brand
Quoted 2 lines · Joshua Hudson

This patch is the sum total of all that I had to change in the kernel VFS layer to support hard links to directories

Can't be done, as it creates the possibility of loops.

Don't do that then?

Exactly.

Quoted 2 lines
Quoted 2 lines

Detecting unconnected subgraphs uses a /lot/ of memory; and much worse, you have to stop (almost) all filesystem activity while doing it.

I know.

I just decided the price is worth it.

In my filesystem, any attempt to create a loop of hard links is detected and cancelled. Unlinking a directory requires it to be empty if the last link is being removed. "." and ".." links are counted separately from real links, so that is easy.

#4 lore raw
Quoted 12 lines · Joshua Hudson
Quoted 9 lines · Bodo Eggert
Quoted 5 lines · Horst H. von Brand
Quoted 2 lines · Joshua Hudson

This patch is the sum total of all that I had to change in the kernel VFS layer to support hard links to directories

Can't be done, as it creates the possibility of loops.

Don't do that then?

Exactly.

Quoted 8 lines
Quoted 2 lines
Quoted 2 lines

Detecting unconnected subgraphs uses a /lot/ of memory; and much worse, you have to stop (almost) all filesystem activity while doing it.

I know.

I just decided the price is worth it.

In my filesystem, any attempt to create a loop of hard links is detected and cancelled.

Can you elaborate a bit on this exciting mechanism? Obviously an ability to efficiently detect loops would be a break-through in a reference-counted garbage collection, somehow missed for last 40 years. :-)

Quoted 3 lines

Unlinking a directory requires it
to be empty if the last link is being removed. "." and ".." links are counted separately from real links, so that is easy.

Nikita.

#5 lore raw
Quoted 8 lines · Nikita Danilov
Quoted 2 lines · Joshua Hudson

In my filesystem, any attempt to create a loop of hard links is detected and cancelled.

Can you elaborate a bit on this exciting mechanism? Obviously an ability to efficiently detect loops would be a break-through in a reference-counted garbage collection, somehow missed for last 40

It's actually pretty trivial to do if it's a toy filesystem and all the relevant inodes are in-memory already. The hard-to-solve part is getting around the (apparent) need to walk across essentially the entire tree structure making sure that you aren't creating a loop. This can get rather performance piggy - even /home on my laptop has some 400K inodes on it, and a 'find /home -type d' takes 28 seconds. That's a *long* time to lock and freeze a filesystem.

Where it gets *really* messy is that it isn't just mkdir that's the problem - once you let there be more than one path from the fs root to a given directory, it gets *really* hard to make sure that any given 'mv' command isn't going to to screw things up (is 'mv a/b/c/d ../../w/z/b' safe? How do you know, without examining a *lot* of stuff under a/ and ../../w/?

#6 lore raw
Quoted 10 lines · On 7/24/06, [email protected] <[email protected]> wrote:
Quoted 8 lines · Nikita Danilov
Quoted 2 lines · Joshua Hudson

In my filesystem, any attempt to create a loop of hard links is detected and cancelled.

Can you elaborate a bit on this exciting mechanism? Obviously an ability to efficiently detect loops would be a break-through in a reference-counted garbage collection, somehow missed for last 40

Quoted 7 lines

It's actually pretty trivial to do if it's a toy filesystem and all the relevant inodes are in-memory already. The hard-to-solve part is getting around the (apparent) need to walk across essentially the entire tree structure making sure that you aren't creating a loop. This can get rather performance piggy - even /home on my laptop has some 400K inodes on it, and a 'find /home -type d' takes 28 seconds. That's a *long* time to lock and freeze a filesystem.

Actually, I walk from the source inode down to try to find the target inode. If not found, this is not attempting to create a loop. Should be obvious that the average case is much less than the whole tree.

Quoted 6 lines

Where it gets *really* messy is that it isn't just mkdir that's the problem - once you let there be more than one path from the fs root to a given directory, it gets *really* hard to make sure that any given 'mv' command isn't going to to screw things up (is 'mv a/b/c/d ../../w/z/b' safe? How do you know, without examining a *lot* of stuff under a/ and ../../w/?

mv /a/b/c/d ../../w/z/b is implemented as this in the filesystem:
ln /a/b/c/d ../../w/z/b && rm /a/b/c/d

So what it's going to do is try to find z under /a/b/c/d.

Oh, and Nakita's right about the NFS server stuff. Actually, I think the current filesystem I use for this is totally incompatible with NFS (cannot call d_splice_alias on directory dnodes) so that doesn't concern me.

#7 lore raw
Quoted 18 lines · Joshua Hudson
Quoted 9 lines · On 7/24/06, [email protected] <[email protected]> wrote:
Quoted 7 lines · Nikita Danilov
Quoted 2 lines · Joshua Hudson

In my filesystem, any attempt to create a loop of hard links is detected and cancelled.

Can you elaborate a bit on this exciting mechanism? Obviously an ability to efficiently detect loops would be a break-through in a reference-counted garbage collection, somehow missed for last 40

Quoted 7 lines

It's actually pretty trivial to do if it's a toy filesystem and all the relevant inodes are in-memory already. The hard-to-solve part is getting around the (apparent) need to walk across essentially the entire tree structure making sure that you aren't creating a loop. This can get rather performance piggy - even /home on my laptop has some 400K inodes on it, and a 'find /home -type d' takes 28 seconds. That's a *long* time to lock and freeze a filesystem.

Quoted 4 lines

Actually, I walk from the source inode down to try to find the target inode. If not found, this is not attempting to create a loop. Should be obvious that the average case is much less than the whole tree.

You have to consider the worst case... and /that/ one is very bad.

Quoted 11 lines
Quoted 6 lines

Where it gets *really* messy is that it isn't just mkdir that's the problem - once you let there be more than one path from the fs root to a given directory, it gets *really* hard to make sure that any given 'mv' command isn't going to to screw things up (is 'mv a/b/c/d ../../w/z/b' safe? How do you know, without examining a *lot* of stuff under a/ and ../../w/?

mv /a/b/c/d ../../w/z/b is implemented as this in the filesystem:
ln /a/b/c/d ../../w/z/b && rm /a/b/c/d

So what it's going to do is try to find z under /a/b/c/d.

What if the ln(1) creates a loop, that the rm(1) then breaks? I.e., move a directory nearer to the root?

Also note that with your idea '..' becomes ambiguous, as w might have /lots/ of parents here.

Quoted 4 lines

Oh, and Nakita's right about the NFS server stuff. Actually, I think the current filesystem I use for this is totally incompatible with NFS (cannot call d_splice_alias on directory dnodes) so that doesn't concern me.

Anything that isn't even NFS-capable is almost useless, IMVHO. Unless you come up with a successor to NFS in tandem, that is.

Signature · 4 lines
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513
#8 lore raw
In reply to Joshua Hudson
Quoted 4 lines · Joshua Hudson

On 7/24/06, [email protected] <[email protected]> wrote:

Actually, I walk from the source inode down to try to find the target inode. If not found, this is not attempting to create a loop.

The problem is that the "target inode" may not be the one obviously causing the loop - you may be trying to link a directory into a/b/c, while the loop is caused by a link from a/b/c/d/e/f/g back up to someplace.

Consider:

function mkdir_tree(foo) {
for i=1,3 do
for j=1,3 do
for k=1,3 do

	mkdir ${foo}/a${i}/b${j}/c${k}
}

mkdir_tree(x)
mkdir_tree(y)
mkdir_tree(z)

ln x/a2/b3/c3/d1 y
ln x/a1/b3/c3/d2 y
ln y/a1/b1/c3/d1 z
ln y/a1/b1/c2/d2 z
ln y/a1/b2/c1/d3 z

Now - ln z/a3/b1/c3/d1 x - how many directories do you need to examine to tell if this is a loop? Is it still a loop if I rm z/d1 first? or z/d2? or do I need to remove z/d1 through z/d3 to prevent a loop? Can I leave z/d1 there but remove y/a1/b2/c3/d1 instead?
Does your answer change if somebody did 'ln y/a1/b2/c4 z/a1/b3/d7'?

How many places would you have to look if I didn't give you a cheat sheet of the ln commands I had done? Yes, you have to search *every* directory under x, y, and z. All 120 of them. And this is an artificially small directory tree. Think about a /usr/src/ that has 4 or 5 linux-kernel trees in it, with some 1,650 directories per tree...

Quoted 2 lines

Should be obvious that the average case is much less than the whole tree.

"The average case" is the one where the feature isn't used. When you actually *use* it, you get "not average case" behavior - not a good sign.

Quoted 7 lines
Quoted 2 lines

to screw things up (is 'mv a/b/c/d ../../w/z/b' safe? How do you know, without examining a *lot* of stuff under a/ and ../../w/?

mv /a/b/c/d ../../w/z/b is implemented as this in the filesystem:
ln /a/b/c/d ../../w/z/b && rm /a/b/c/d

So what it's going to do is try to find z under /a/b/c/d.

Even if that's sufficient (which it isn't), it's going to be painful to lock the filesystem for 20 or 30 seconds while you walk everything to make sure there's no problem.

#9 lore raw
Quoted 11 lines · On 7/24/06, [email protected] <[email protected]> wrote:
Quoted 4 lines · Joshua Hudson

On 7/24/06, [email protected] <[email protected]> wrote:

Actually, I walk from the source inode down to try to find the target inode. If not found, this is not attempting to create a loop.

The problem is that the "target inode" may not be the one obviously causing the loop - you may be trying to link a directory into a/b/c, while the loop is caused by a link from a/b/c/d/e/f/g back up to someplace.

Consider:

[case of 3^4 directories ]

Quoted 1 line

Yes, you have to search *every* directory under x, y, and z.

With a mesh graph like that one, you are right. Rather like my test cases to see if the loop-detection algorithm is working.

Quoted 3 lines

And this is an artificially small
directory tree. Think about a /usr/src/ that has 4 or 5 linux-kernel trees in it, with some 1,650 directories per tree...

Interesting case.

Quoted 7 lines
Quoted 3 lines

Should be obvious that the average case is much less than the whole tree.

"The average case" is the one where the feature isn't used. When you actually *use* it, you get "not average case" behavior - not a good sign.

My use cases were generally about creating links at the twig level. In my consideration, there would be two or more topical trees arranged by different criteria, and they would bottom out at the topics, which are directories that hold a number of documents.

A document might be a single file, a few files together, or a directory that contains a few files that should alwas be together. I suppose that an entire source tree could be considered one document, and there lies the flaw.

This system is an attempt to replace a system of hard links to files that didn't work because certain MS applications use rename and create when saving files. The filesystem is intended to be exported over smbfs. It is still very-much a single-user scheme, which is why the bad worst case didn't really concern me.

Quoted 9 lines
Quoted 5 lines

mv /a/b/c/d ../../w/z/b is implemented as this in the filesystem:
ln /a/b/c/d ../../w/z/b && rm /a/b/c/d

So what it's going to do is try to find z under /a/b/c/d.

Even if that's sufficient (which it isn't), it's going to be painful to lock the filesystem for 20 or 30 seconds while you walk everything to make sure there's no problem.

Maybe someday I'll work out a system by which much less is locked. Conceptually, all that is requred to lock for the algorithm to work is creating hard-links to directories and renaming directories cross-directory.

Quoted 1 line

(which it isn't)

Counterexample? I should swear that any cycle created by rename must pass through the new parent into the victim and back to the new parent.

#10 lore raw
Quoted 6 lines · Joshua Hudson

On 7/24/06, [email protected] <[email protected]> wrote:

[case of 3^4 directories ]

Quoted 1 line

Yes, you have to search *every* directory under x, y, and z.

With a mesh graph like that one, you are right. Rather like my test cases to see if the loop-detection algorithm is working.

And why bother allowing it, if a mesh like that isn't something you want to support and do it well?

Quoted 4 lines
Quoted 3 lines

And this is an artificially small
directory tree. Think about a /usr/src/ that has 4 or 5 linux-kernel trees in it, with some 1,650 directories per tree...

Interesting case.

Not an "interesting case" - that's the real world. You allow hard links to directories, somebody on this list *is* going to hardlink their directory of driver code into several kernel trees so they can regression test compiles against multiple trees.

You don't want to deal with the results of allowing that, don't allow that. ;)

Quoted 10 lines
Quoted 5 lines
Quoted 1 line

So what it's going to do is try to find z under /a/b/c/d.

Even if that's sufficient (which it isn't), it's going to be painful to lock the filesystem for 20 or 30 seconds while you walk everything to make sure there's no problem.

Maybe someday I'll work out a system by which much less is locked. Conceptually, all that is requred to lock for the algorithm to work is creating hard-links to directories and renaming directories cross-directory.

You need to lock a *lot* of stuff - otherwise 2 separate links can race and form a loop, even though they are operating in very different parts of the directory graph.

You can't even answer the question "Will a proposed link cause a loop?" without locking the tree, since you have to search the whole tree. An apparently unrelated change in a part of the tree you've already searched can cause a loop because what you started with isn't what you finished with (see the unrelated thread about locking or copying the process list so 'ps' doesn't race for the sort of issues involved).

Quoted 5 lines
Quoted 1 line

(which it isn't)

Counterexample? I should swear that any cycle created by rename must pass through the new parent into the victim and back to the new parent.

Quoted 1 line

So what it's going to do is try to find z under /a/b/c/d.

I meant that 'z' may not be "under" a/b/c/d in the conventional sense - the criterion is the much flabbier "must be reachable from" (which leads to the "have to enumerate the whole frikking filesystem" issue). d could contain a link back "up" to e/f/g, which links back "down" to 'h/i/j/k", and h/i/j/k/l has a link back "up" to something that eventually leads to z.

And you still haven't explained what '..' means in this context. I'm sure programmers will be *thrilled* to have to deal with this:

mkdir a b c
mkdir b/a b/d a/a
ln b/a a/z
ln c/b b/a
# Now watch the fun with a context-sensitive '../a':
cd a/z; cd ../a <- succeeds, but leaves you elsewhere cd b/a; cd ../a <- succeeds, and leaves you where you started cd c/a; cd ../a <- fails

(To be fair, most programs that have issues with this are racy against renames of ../a already - but this one can cause fun and games even on a filesystem mounted r/o and apparently immutable...)

#11 lore raw
In reply to Joshua Hudson

Joshua Hudson <[email protected]> wrote:

[...]

Quoted 4 lines

Maybe someday I'll work out a system by which much less is locked. Conceptually, all that is requred to lock for the algorithm to work is creating hard-links to directories and renaming directories cross-directory.

Some 40 years of filesystem development without finding a solution to that conundrum would make that quite unlikely, but you are certainly welcome to try.

Quoted 4 lines
Quoted 1 line

(which it isn't)

Counterexample? I should swear that any cycle created by rename must pass through the new parent into the victim and back to the new parent.

Right. The problem is that the fan-out can be humongous. In the worst case (which you /have/ to handle right!) you need to look over /all/ the directories in the filesystem. Meanwhile, you can't allow any operation that changes the graph. Have you run fsck(8) lately? That should give you an order-of-magnitude estimate for the time it could take...

Yes, in the "avergage case" it will be much, much less, but that is little comfort for people who get bitten by "not so average" cases.

Remember that one of the things that made Linus unhappy with Minix was exactly that the filesystem was single-threaded. Today's requirements for Linux filesystem performance are /much/ higer than the ones of a lone hobby user...

Signature · 4 lines
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

A message that is not in the archive (sent off-list or not yet received): [email protected]

#13 lore raw
Quoted 8 lines · Bodo Eggert
Quoted 5 lines · Horst H. von Brand
Quoted 2 lines · Joshua Hudson

This patch is the sum total of all that I had to change in the kernel VFS layer to support hard links to directories

Can't be done, as it creates the possibility of loops.

Don't do that then?

Stop /everything/ to make sure no concurrent activity creates a loop, while checking the current mkdir(2) doesn't create one?

Quoted 10 lines
Quoted 6 lines

The "only files can
be hardlinked" idea makes garbage collection (== deleting of unreachable objects) simple: Just check the number of references.

Detecting unconnected subgraphs uses a /lot/ of memory; and much worse, you have to stop (almost) all filesystem activity while doing it.

In order to disconnect a directory, you'd have to empty it first, and after emptying a directory, it won't be part of a loop. Maybe emtying is the problem ...

What does "emptying a directory" mean if there might be loops?

Quoted 1 line

This feature was implemented,

Never in my memory of any Unix (and lookalike) system in real use (I've seen a few).

Quoted 2 lines

and I asume it was removed for a reason.
Can somebody remember?

See my objections.

Signature · 4 lines
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513
#14 lore raw
Quoted 6 lines · you
Quoted 5 lines · Bodo Eggert
Quoted 4 lines · Horst H. von Brand
Quoted 2 lines · Joshua Hudson

This patch is the sum total of all that I had to change in the kernel VFS layer to support hard links to directories

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

Can't be done, as it creates the possibility of loops.

Don't do that then?

Stop /everything/ to make sure no concurrent activity creates a loop, while checking the current mkdir(2) doesn't create one?

This doesn't seem that big of an issue for people to be up in arms about. You wouldn't have to stop /everything/, would you, just have an in kernel mutex in vfs_mkdir. It's not the most commonly used system call in the book -- meaning serializing the checking/creating of new directories would not really hamper your system /that/ much.

Personally, I don't think hard linked directories are necessary or even that interesting, but they certainly aren't impossible to do. I suppose there might be some specialty filesystem that might like to do hardlinked directories and I don't think the vfs core should make it difficult.

--Vernon

Quoted 22 lines
Quoted 10 lines
Quoted 6 lines

The "only files can
be hardlinked" idea makes garbage collection (== deleting of unreachable objects) simple: Just check the number of references.

Detecting unconnected subgraphs uses a /lot/ of memory; and much worse, you have to stop (almost) all filesystem activity while doing it.

In order to disconnect a directory, you'd have to empty it first, and after emptying a directory, it won't be part of a loop. Maybe emtying is the problem ...

What does "emptying a directory" mean if there might be loops?

Quoted 1 line

This feature was implemented,

Never in my memory of any Unix (and lookalike) system in real use (I've seen a few).

Quoted 2 lines

and I asume it was removed for a reason.
Can somebody remember?

See my objections.

#15 lore raw
In reply to Horst H. von Brand
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

"Horst" == Horst H von Brand <[email protected]> writes:

Quoted 1 line · Horst> Bodo Eggert <[email protected]> wrote:
Quoted 1 line

This feature was implemented,

Horst> Never in my memory of any Unix (and lookalike) system in real Horst> use (I've seen a few).

Back in edition 5 UNIX, there were /etc/link and /etc/unlink that could operate on directories, if and only if you were root. I used to use them to deliberately muck up file systems for system administration courses...

--
Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au
http://www.ertos.nicta.com.au ERTOS within National ICT Australia

#16 lore raw
In reply to a message not in the archive
Quoted 10 lines · Bodo Eggert
Quoted 9 lines · Horst H. von Brand

Joshua Hudson <[email protected]> wrote:

[...]

Quoted 4 lines

Maybe someday I'll work out a system by which much less is locked. Conceptually, all that is requred to lock for the algorithm to work is creating hard-links to directories and renaming directories cross-directory.

Quoted 6 lines
Quoted 3 lines

Some 40 years of filesystem development without finding a solution to that conundrum would make that quite unlikely, but you are certainly welcome to try.

There is a simple solution against loops: No directory may contain a directory with a lower inode number.

This is a serious restriction...

Quoted 2 lines

Off cause this would interfere with normal operations, so you'll allocate all normal inodes above e.g. 0x800000 and don't test between those inodes.

And allow loops there? I don't see how that solves anything...

Quoted 3 lines

If you want to hardlink, you'll use a different (privileged) mkdir call that will allocate a choosen low inode number. This is also required for the parents of the hardlinked directories.

Argh... even /more/ illogical restrictions!

Quoted 2 lines

You can also use the generic solution: Allow root to shoot his feet, and make sure the gun works correctly.

;-)

Signature · 4 lines
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513
#17 lore raw
Quoted 11 lines · Horst H. von Brand
Quoted 10 lines · Bodo Eggert
Quoted 9 lines · Horst H. von Brand

Joshua Hudson <[email protected]> wrote:

[...]

Quoted 4 lines

Maybe someday I'll work out a system by which much less is locked. Conceptually, all that is requred to lock for the algorithm to work is creating hard-links to directories and renaming directories cross-directory.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Some 40 years of filesystem development without finding a solution to that conundrum would make that quite unlikely, but you are certainly welcome to try.

There is a simple solution against loops: No directory may contain a directory with a lower inode number.

This is a serious restriction...

That's why I relax it in the next paragraph, so you'll only have to deal with inode numbers iff you want to hardlink directories.

Quoted 4 lines
Quoted 2 lines

Off cause this would interfere with normal operations, so you'll allocate all normal inodes above e.g. 0x800000 and don't test between those inodes.

And allow loops there? I don't see how that solves anything...

No. Don't allow dir-hardliks there, so you can't create loops so you can freely create them without risking loops.

Quoted 5 lines
Quoted 3 lines

If you want to hardlink, you'll use a different (privileged) mkdir call that will allocate a choosen low inode number. This is also required for the parents of the hardlinked directories.

Argh... even /more/ illogical restrictions!

If no (hardlink) directory may contain a lower inode directory, all parents need to have a low inode.

A legal tree would e.g. look like this:

1-+-100
| +-10001
| `-10002

  +-101
  | +-10101
  | +-10002
  | `-10102

`-10101

In order to create a loop, you'd e.g. need to link 101 into 10002. You can't, because they are ordered.

Directories above 0x800000 aren't ordered except being greater than low inodes, so you can create normal directories anywhere you desire, but you obviously can't hardlink them.

Signature · 1 line
It's redundant! It's redundant!