Directories, and the Shapes They Take

Deleting a directory needs a policy, and a question asks for both options. Either a directory must be empty before it can be deleted, and the user clears it first, or the system deletes everything inside it recursively, which is convenient and dangerous. Systems offer both, under different names.

Shape four: an acyclic graph directory

Let two directories share one file, or one subdirectory, so the structure is no longer a tree. Two programmers on one project need the same file to be in both their directories, and a copy is not the same thing: a copy does not change when the other person edits it.

The three problems, and this is what a question asks for

The reference count is the answer to the deletion problem, and it is the same counter as the open count of Chapter ninety nine and the shared frame count of Chapter seventy seven. The idea appears three times in this module for the same reason: something is shared, and the last user must be the one who frees it.

Demonstrated on the lab machine

$ printf 'the contents\n' > report.txt
$ ln report.txt copy-of-report.txt
$ stat -c '%n has %h name(s) and inode %i' report.txt copy-of-report.txt | sed 's/inode [0-9]*/inode N/'
report.txt has 2 name(s) and inode N
copy-of-report.txt has 2 name(s) and inode N
$ stat -c %i report.txt copy-of-report.txt | sort -u | wc -l
1
$ ln -s report.txt shortcut.txt
$ stat -c '%n is a %F of %s bytes' shortcut.txt
shortcut.txt is a symbolic link of 10 bytes
$ rm report.txt
$ echo "after removing the first name, the second still reads:"; cat copy-of-report.txt
after removing the first name, the second still reads:
the contents
$ stat -c '%n now has %h name(s)' copy-of-report.txt
copy-of-report.txt now has 1 name(s)
$ cat shortcut.txt
cat: shortcut.txt: No such file or directory

Every line of the theory above is in that transcript.

The link count of a directory

The cleanest proof that . and .. are ordinary entries.

$ mkdir project
$ stat -c 'a new directory has a link count of %h' project
a new directory has a link count of 2
$ mkdir project/chapter1 project/chapter2
$ stat -c 'with two subdirectories it has %h' project
with two subdirectories it has 4
$ ls -a project
.  ..  chapter1  chapter2

An empty directory has two links, not one. Its name in the parent is one, and its own . entry is the other. Each subdirectory then adds one more, because each holds a .. entry pointing back. Two subdirectories therefore make four, and the arithmetic is exact:

So a directory's link count is 2 plus the number of subdirectories, which is a fact worth knowing: it tells you how many subdirectories a directory has without listing it.

Shape five: a general graph directory

Allow a link from a directory to one of its own ancestors, and the structure has a cycle.

UNIX takes the first way out: a hard link to a directory is not allowed, so the graph of hard links is acyclic and the link count can be trusted. Symbolic links can make cycles, and the answer there is the second way out: the system refuses after following a fixed number of links.

Distinctions that carry marks

What it does not mean

A directory is not a list of files. It is a list of names and identifiers; the files are elsewhere.

A hard link is not a copy. There is one file. Editing through either name changes the same bytes.

Deleting a name is not deleting a file. The file goes when the reference count reaches zero.

A symbolic link is not free. It is a file with its own inode and its own block, holding the path.

A general graph is not a richer tree. It is a structure whose traversal may not end and whose space may never be freed, which is why systems prevent it.

Quick revision

• A directory is a symbol table from names to file identifiers, and it is itself a file.
• Operations: search, create, delete, list, rename, traverse.
• Single level: one directory, so names must be unique machine wide and there is no

grouping.

• Two level: a master file directory of users, each with a user file directory.

Solves collisions between users; needs a search path for system files.

• Tree: directories inside directories, with a root, absolute and relative paths,

and a current directory per process. Deleting a directory: empty only, or recursive.

• Acyclic graph: sharing by hard links or symbolic links. Three problems:

several path names, deletion, and dangling links. Deletion is solved by a reference count freed at zero.

• Measured: a hard link gives one inode with two names; a symbolic link is a 10 byte file

holding the path; after removing one name the count is 1 and the contents survive; the symbolic link then dangles.

• A directory's link count is 2 plus its number of subdirectories: an empty one has 2,

and with two subdirectories 1 + 1 + 2 = 4.

• General graph: cycles make traversals endless and reference counts never zero. Ways out:

links to files only, a link limit, cycle detection, or garbage collection. UNIX forbids hard links to directories.

Test yourself

1. What is a directory, and what is it stored as? A symbol table translating file names into

the identifiers the file system uses, stored as a file like any other.

1. Why is a single level directory unusable? Every name must be unique across the whole

machine and there is no way to group files.

1. What does a two level directory solve, and what does it still lack? It stops users

colliding over names by giving each a directory under a master file directory; it still offers no grouping within a user, and system files need a search path.

1. Distinguish an absolute path from a relative path. An absolute path starts at the root and

means the same thing in every process; a relative path starts at the process's current working directory.

1. Give the two policies for deleting a non empty directory. Refuse unless it is empty, or

delete its contents recursively.

1. Name the three problems of an acyclic graph directory and the answer to the second.

Several absolute path names for one file, deletion, and dangling links; deletion is handled by a reference count in the file, freed only when it reaches zero.

1. How do a hard link and a symbolic link differ? A hard link is another directory entry for

the same file and counts towards its link count; a symbolic link is a separate small file holding a path, does not count, and dangles if the target goes. Only the symbolic link can cross file systems or point at a directory.

1. A directory has a link count of 5. How many subdirectories does it have? Three: the count

is 2 plus the number of subdirectories, one for its name in the parent, one for its own dot entry, and one for each child's dot dot.

1. Why are cycles in a directory structure dangerous, and what does UNIX do about it? A

traversal may never end and reference counts may never reach zero, so space is never freed; UNIX forbids hard links to directories and limits how many symbolic links it will follow.