Directory link counts and a
In the beginning, Unix directories were remarkably non-special. One
of the ways that they were non-special is that connections between
directories were not special in any way; a directory entry for a
directory was just a hard link to the directory's inode, the same as
with any other sort of inode. This applied to the two special names
.. too; each of them was a regular directory entry, the first a
hard link to the directory itself and the second a hard link to the
(Thus if you tried hard or had bad luck with disk corruption it was
possible to wind up with a directory where
chdir(".") would put you in
a different directory, because the
. entry was pointing to the wrong
So far this is just Unix being simple and regular. But it had an
interesting consequence: the inode link count for directories meant
something. A directory always had at least two links (one for its own
. entry, one for its entry in its parent directory) and then it had
one more link for every subdirectory it had (each subdirectory had a
.. entry pointing back to the directory).
This leads immediately to two related optimizations for
other directory walkers:
- when you encounter a directory that has a link count of 2, you know
that it has no subdirectories and you do not need to
stat()any of its directory entries at all.
- when you encounter a directory with a link count larger than 2, you
can keep track of how many subdirectories you've seen; once you've
seen N-2, you can stop
stat()'ing all the remaining directory entries because none of them can point to subdirectories.
(These are the clever optimizations I was talking about yesterday.)
There are two flaws in these optimizations. The first is that they assume that you're dealing with a sufficiently Unix-like filesystem to actually have valid directory link counts. This is no longer always the case, although I believe that it's still true for all serious Unix filesystems.
The second is that they assume that you're dealing with static,
unchanging directories where you can look at the link count once and
have it remain valid for your entire scan of the directory. This is
not necessarily the case. You can sort of get around this by repeatedly
fstat()'ing the directory; this is still a system call, but at least
it isn't going to touch the disk since you're guaranteed that the
directory's inode is in memory while you have it open.
(I don't consider it a flaw that these optimizations can break in the face of sufficient filesystem corruption. Nothing works in the face of sufficient filesystem corruption.)