Wandering Thoughts archives

Directory link counts and a find trick

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 . and .. 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 parent directory.

(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 inode.)

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 find and 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.)