Linux: How does hard-linking to a directory work?

Question

I'm aware that Linux does not allow hard-linking to a directory. I read somewhere,

1. that this is to prevent unintentional loops (or graphs, instead of the more desirable tree structure) in the file-system.

2. that some *nix systems do allow the root user to hard-link to directories.

So, if we are on one such system (that does allow hard-linking to a directory) and if we are the root user, then how is the parent directory entry, .., handled following the deletion of the (hard-link's) target and its parent?

a (200)
\-- .  (200)
\-- .. (100)
\-- b  (300)
|   \-- .  (300)
|   \-- .. (200)
|   \-- c  (400)
|       \-- .  (400)
|       \-- .. (300)
|       \-- d  (500)

 <snip>

|
\-- H (400)

(In the above figure, the numbers in the parentheses are the inode addresses.)

If a/H is an (attempted) hard-link to the directory a/b/c, then

1. What should be the reference count stored in the inode 400: 2, 3, or 4? In other words, does hard-linking to a directory increases the reference count of the target directory's inode by 1 or by 2?

2. If we delete a/b/c, the . and .. entries in inode 400 continue to point to valid inodes 400 and 300, respectively. But what happens to the reference count stored in inode 400 if the directory tree a/b is recursively deleted?

Even if the inode 400 could be kept intact via a non-zero reference count (of either 1 or 2 - see the preceding question) in it, the inode address corresponding to .. inside inode 400 would still become invalid!

Thus, after the directory tree b stands deleted, if the user changes into the a/H directory and then does a cd .. from there, what is supposed to happen?

Note: If the default file-system on Linux (ext4) does not allow hard-linking to directories even by a root user, then I'd still be interested in knowing the answer to the above question for an inode-based file-system that does allow this feature.

Answer 1

Hard links to directories aren't fundamentally different to hard links for files. In fact, many filesystems do have hard links on directories, but only in a very disciplined way.

In a filesystem that doesn't allow users to create hard links to directories, a directory's links are exactly

1. the . entry in the directory itself;
2. the .. entries in all the directories that have this directory as their parent;
3. one entry in the directory that .. points to.

An additional constraint in such filesystems is that from any directory, following .. nodes must eventually lead to the root. This ensures that the filesystem is presented as a single tree. This constraint is violated on filesystems that allow hard links to directories.

Filesystems that allow hard links to directories allow more cases than the three above. However they maintain the constraint that these cases do exist: a directory's . always exists and points to itself; a directory's .. always points to a directory that has it as an entry. Unlinking a directory entry that is a directory only removes it if it contains no entry other than . and ...

Thus a dangling .. cannot happen. What can go wrong is that a part of the filesystem can become detached. If a directory's .. pointing to one of its descendants, so that ../../../.. eventually forms a loop. (As seen above, filesystems that don't allow hard link manipulations prevent this.) If all the paths from the root to such a directory are unlinked, the part of the filesystem containing this directory cannot be reached anymore, unless there are processes that still have their current directory on it. That part can't even be deleted since there's no way to get at it.

GCFS allows directory hard links and runs a garbage collector to delete such detached parts of the filesystem. You should read its specification, which addresses your concerns in details. This is an interesting intellectual exercise, but I don't know of any filesystem that's used in practice that provides garbage collection.

Answer 2

Hard-linking a directory (when permitted) works very much the same as hard-linking a plain file.  So, hard-linking always increases the link count by one, and so, in your question #1, the link count would increase from 2 to 3.

Question #2 is a little more mind-bending, and it depends on how smart rmdir is.  Normally, if you delete directory a/b/c, the “rmdir” program unlinks

• a/b/c/.   - inode 400
• a/b/c/.. - inode 300
• a/b/c      - inode 400

But remember -- c and H are the same directory (inode), so it might be more precise to reframe the above list as

• (inode 400)/.   - inode 400
• (inode 400)/.. - inode 300
• (inode 300)/c   - inode 400

In other words, the . and .. entries will have been deleted from inode 400 (known as a/b/c and a/h), so your assumption in question #2 may be wrong – directory H might continue to exist, but be completely empty (not even any . and .. entries).

But another possibility is that “rmdir” will see that the link count on c is 3 and might unlink only a/b/c, and not the entries in c (inode 400).  In that case, think how it works with plain files.  (I assume that you basically understand this.)

• If you create file antelope, hard-link it to gazelle, and then delete antelope, the file still exists under the name gazelle.

• If you create file dir1/antelope, hard-link it to dir2/gazelle, and then delete dir1/antelope, the file still exists under the name dir2/gazelle.

• OK, substitute b for antelope, a for dir1, .. for gazelle, and H for dir2. Then H/.. (inode 300) would continue to exist, with a link count of 1, but (as in the other scenario) it would be completely empty (not even any . and .. entries).

This sort of mess is why hard-linking directories is strongly discouraged.