5

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.

  • 2
    I know I've run into hard-linked directories in the distant past - I still have the mental scars from trying to figure out what cd .. put my program some weird directory. I think SunOS 4.1.x allowed this, and possibly Solaris 2.2. System Vr3 might have allowed it. – Bruce Ediger Jan 11 '14 at 14:24
  • 1
    And I'm in the process of getting those scars right now! If you're building your own filesystem, you can always establish a known policy/behavior (of, say, jumping to the default dir of your filesystem if there's such a thing even, or cd'ing to $HOME, etc). However, I'm quite curious to know how the 'standard' or 'well-known' filesystems that do support this feature really handle the reference counting of the target dir and the cd .. business. – Harry Jan 11 '14 at 14:53
  • 1
    you ask good questions, I just don't know the answer. You might be able to use NetBSD or OpenBSD to find out. Those two are the closest to old SunOS 4.1.x that still run on modern hardware. My last SunOS4.1.4 machine went to recycling years ago, or I'd give it a try. – Bruce Ediger Jan 11 '14 at 15:30
  • some implementations do allow directory hardlinks Why are hard links to directories not allowed in UNIX/Linux? – phuclv Jul 21 '18 at 12:51
3

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.

  • 'Special' thanks for mentioning GCFS - I never knew it existed. – Harry Jan 12 '14 at 2:36
  • Aren't point 1 & 3 same always? If not, In which cases would they differ? – Vishal Sahu Dec 6 '15 at 18:02
  • 1
    @VishalSahu Points 1, 2 and 3 are the same inode — that's what being links to the same file means. They're obviously all different directory entries since they're all located in different directories (1. the directory itself; 2. its child directories; 3. its parent). – Gilles Dec 6 '15 at 18:04
3

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.

  • +1 for showing the other possibility of the dir completely empty -- without even the . and .. -- in some implementation of the feature. Being 'discouraged' to use a feature is one thing (like, it's discouraged to work as root on a *nix box for ordinary work), but the mechanics of the feature, the design behind it, is another. My question was more on the design of the feature and side-effects (if any) if it were supported by a system and if the user were a root user. Eg, how would a textbook describe this feature, notwithstanding the caveats that would come with it? – Harry Jan 12 '14 at 1:24
  • @Harry Here you're assuming that the filesystem allows deleting a non-empty directory, which is very different from allowing hard links to directories. Some unix variants allow hard links to directories, but they enforce that if directory A's .. points to B then B contains an entry for A. – Gilles Jan 12 '14 at 1:38
  • @Gilles I doubt if I was assuming the deletion of non-empty dirs. I could restate the deletion part like this if you like: First, delete the file a/b/c/d, then the dir a/b/c, and finally the dir a/b. So, my question is -- design-wise -- what should happen to a process that had earlier cded itself into a/H but now attempts a cd ..? Not sure if I followed your last sentence: Doesn't B always contain an entry for A? – Harry Jan 12 '14 at 1:48
  • @Harry “Doesn't B always contain an entry for A?” No; in your example, a/H is a hard-link to a/b/c, so they are the same inode (#400). And inode 400 contains entries (., 400), (.., 300), and maybe (d, 500) if you haven’t deleted it yet. So a/H has a .. entry that points to inode 300, which is accessible from the file system root as a/b. But, if you’ve removed a/b/c, then inode 300 (a/b) no longer contains an entry for inode 400. – Scott Jan 12 '14 at 21:05
  • @Harry Regarding your first comment: I thought I did answer your question on the design of the feature and side-effects (if any) if it were supported by a system and if the user were a root user. To ask how a textbook would describe hard links is a bit too broad for Stack Exchange, but if there’s some particular technical information that you still want to know, go ahead and ask. – Scott Jan 12 '14 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.