The Stack Overflow podcast is back! Listen to an interview with our new CEO.
6 of 6 added 1189 characters in body

You're confused. rmdir simply doesn't care about link counts. The logic is quite straightforward.

Once a file has a link count of 0, and additionally, no running processes with a reference (file descriptor or current directory), it will be truly deleted. That's the point when the disk space can be re-used for something else [*].

Directories are a file. But unlinking (removing them from their parent) requires more consideration than other types of file. We must make sure each child of the directory is unlinked as well. Otherwise, we could lose the chance to update the children's link count. We would lose that disk space permanently.

So we don't let users call unlink on a directory. Instead, they must use the special-purpose rmdir. Calling rmdir differs from unlink in just two ways

  1. It requires that the directory is "empty", which means that its only children are the standard . and .. entries.
  2. It makes sure to unlink these two remaining entries, before it runs unlink on the directory itself.

That's it. There is no other magic. rmdir is not deferred until the condition in point 1 holds. rmdir either succeeds or fails at the time it is called. Nor is the condition based on link count in any way.

I find the effect of the . entry on link counts interesting, even though it's not a special case. It's a hard-link to the parent directory, and therefore increases it's link count. This is the explanation for why a newly created directory DIR has a link count of 2. If you then call rmdir DIR, the link count falls back to 0, because it removes both links DIR/. and DIR.

Linux actually allows you to observe the above by running a shell inside the directory, and running ls -ld after the directory has been unlinked (removed from its parent).

Of course ls -ld is shorthand for ls -ld .. . and .. keep working even after the directory entry is removed; in fact modern Linux does not really rely on these on-disk directory entries. I expect the original Unix implementation would not support this. However I believe the reference counts still worked as described above, and did not have a special-case for the removal of a directory.

(How .. continues to work is even more interesting. Discussed in comment below).

In fact it would be very easy for you to look at the original Unix code for rmdir. It was implemented as a user program running with special privileges. Historical unix code is easy to find online. It's one reason I'm so confident about this.

[*] So you can see whether a file has been deleted by looking for a difference in used disk blocks in df . (or i-nodes in df -i .). This approach works nicely in filesystems like Linux ext4. Less traditional filesystems may have more complex optimizations though, which can make it harder to observe.