4.2.33 · D5Operating Systems
Question bank — Directory structure — tree, DAG (hard links, symbolic links)
Before we start, two pictures that everything below leans on.
Picture 1 — a name is not an inode. Directory entries live in directories; the actual file lives in an inode. Names point at inodes; the inode keeps a counter of how many names point at it.
Recall The one fact that unlocks all traps
A directory entry (name) and an inode (data + metadata) are separate things. A name points at an inode; the inode stores a link count — call it — equal to the number of directory entries pointing at it. Hold this picture and most traps dissolve.
Picture 2 — one shared file turns the tree into a DAG. In a pure tree every file has exactly one name (one incoming arrow). The moment two names point at one inode, that node has two incoming arrows — no longer a tree, but still acyclic: a DAG.
Spot the difference visually
Hard link vs symlink at a glance. A hard link is a second name wired straight to the inode ( goes up). A symlink is a tiny separate inode whose data is the text of a path — it does not touch , so deleting the target leaves it dangling.
True or false — justify
True or false: rm file.txt deletes the file's data from disk.
False in general.
rm calls unlink, which removes one name and decrements the inode's link count ; data is freed only when and no process holds it open.True or false: a hard link creates a copy of the file.
False. A hard link is a second name for the same inode — one set of data blocks, two doors into the same room. Editing via either name changes the same bytes.
True or false: creating a symbolic link increases the target's link count.
False. A symlink is its own separate inode storing a path string; the target has no idea the symlink exists, so its link count is untouched. This is why deleting the target leaves the symlink dangling.
True or false: a filesystem with hard links is still a tree.
False. A file reachable by two names has two incoming edges, so it is not a tree. It becomes a DAG — see Graphs — Trees vs DAGs — because directory cycles are forbidden but shared children are allowed.
True or false: you can hard-link a file across two different filesystems.
False. A hard link stores an inode number, which is only meaningful within one filesystem. Crossing filesystems needs a symlink (which stores a path string) — see Mount points and Virtual File System (VFS).
True or false: you can symlink to a directory.
True. A symlink just holds text, so it can point at a directory, a file, or even a non-existent path — no cycle danger for hard-link accounting, though the kernel caps chain depth.
True or false: every directory, even in a "pure tree", contains entries that make the directory graph cyclic.
True. Every directory holds
. (itself) and .. (its parent), so the directory graph technically has cycles. That is precisely why the kernel — not users — manages these and why user directory hard links are banned.True or false: after rm a.txt on a file that also has hard link b.txt, cat b.txt still works.
True.
rm a.txt only drops from 2 to 1; the inode and its data survive because b.txt still references them.True or false: a symlink and its target always share the same inode number.
False. A symlink has its own inode (type
l); the target has a different inode. That is the whole difference from a hard link, which shares the target's inode.True or false: stat on a symlink and stat on its target return the same metadata.
False.
lstat reports the symlink's own metadata (tiny size = length of the path string, type l); following it to the target gives different size, type, and inode. See Unix system calls — link, unlink, symlink, stat.Spot the error
Spot the error: "A hard link points at a path, so if I rename the target the link breaks."
A hard link points at the inode, not a path — renaming or even deleting the original name doesn't touch the data. It's the symlink that stores a path and breaks on rename.
Spot the error: "The link count tells you how many symlinks point to a file."
The link count counts hard links (directory entries pointing at the inode), not symlinks. Symlinks are invisible to ; that's why they can dangle.
Spot the error: "To keep a file alive, keep a symlink to it."
A symlink does not hold a reference in , so it can't keep anything alive. To guarantee survival you need a hard link — see Reference Counting and Garbage Collection.
Spot the error: "When link count reaches 0 the data is freed immediately, no exceptions."
Only if no process has the file open. An open file descriptor is also a reference; the blocks free when and open-count . This is the classic "delete a file a process is still writing" case.
Spot the error: "ls -l shows s.txt -> a.txt, so s.txt is just an alias inode for a.txt."
The
-> and the l type char reveal it's a symlink: a separate inode whose data is the text a.txt. An alias-for-the-same-inode is a hard link and shows no arrow and no l.Spot the error: "Because it's a DAG, I can create a cycle of directories with hard links."
A DAG has no cycles by definition, and the kernel forbids user directory hard links exactly to prevent cycles — otherwise traversal (
find, du) would never terminate.Why questions
Why does the OS separate a file's name from its inode instead of storing the name inside the file?
So that many names can map to one inode (hard links) and so directories can be independent lookup tables. If the name lived in the data, each file could have only one name.
Why is the filesystem a DAG and not a general graph?
Directory cycles are forbidden so traversal terminates and reference counting stays meaningful (a cycle would make "reachable ⇔ " false). Acyclic + shared children = DAG.
Why can't a symlink increment the target's link count even though it "points to" it?
Because the symlink stores only text; the target inode is never consulted at creation time and has no back-pointer. The pointing is resolved lazily at access time via Path Resolution and the namei() routine.
Why does deleting one hard link never lose data but deleting a symlink's target does?
Each hard link is a counted reference, so removing one just decrements the link count by one; other names keep . A symlink is uncounted text, so removing the real name drops to 0 and the symlink now resolves to nothing.
Why does the kernel cap symlink chain depth (typically about 40 hops)?
Symlinks can point at other symlinks, and a symlink can even point (indirectly) back into its own resolution path, creating an infinite loop. Since the acyclicity guarantee only covers hard links, the depth cap is the safety net for symlinks. When the cap is exceeded the kernel returns the error
ELOOP — a Unix error code (from errno.h) meaning literally "too many levels of symbolic links".Why must hard links stay within one filesystem while symlinks can cross?
Hard links store an inode number, valid only inside its own filesystem; symlinks store a path string, which the resolver re-walks from
/ through mount points, so it can land anywhere.Edge cases
What happens to the link count when you ln -s a.txt s.txt (symlink)?
a.txt's link count stays unchanged (e.g. 1). Only s.txt's brand-new inode is created; symlinks never touch the target's count.What is a "dangling" symlink and how is one created?
A symlink whose stored path no longer resolves — created by deleting or renaming the target, or by symlinking to a path that never existed.
cat on it gives "No such file or directory".If a file has link count 2 and one name is rm'd while a process still has it open, what is the state?
drops to 1 and both the remaining name and the open descriptor keep the data fully alive; nothing is freed. (Even at with an open fd, data persists until close.)
What does the link count of a brand-new empty directory equal, and why?
It equals 2: one entry for its name in the parent, plus its own
. entry pointing back at itself. Each subdirectory it later gains adds 1 (via that child's ..).Can a hard link and the file it links to have different permissions or timestamps?
No. Permissions, timestamps, and all metadata live in the shared inode, so every hard link sees identical metadata. A symlink, having its own inode, can differ.
If you cp a symlink, do you get a copy of the link or a copy of the target?
Depends on flags: a plain
cp follows the link and copies the target's data; cp -P (or cp -a) copies the symlink itself (the path-string file). This is a frequent silent trap.Connections
- Inodes and File Metadata
- Path Resolution and the namei() routine
- Reference Counting and Garbage Collection
- Graphs — Trees vs DAGs
- Unix system calls — link, unlink, symlink, stat
- Mount points and Virtual File System (VFS)