General Graph Directories and Cycle Issues
What you'll learn: How unrestricted linking in file systems can create cycles and why they pose serious garbage collection challenges.
Why Cycles Are a Problem
In the acyclic graph directories you just learned about, we carefully avoided cycles—paths that loop back to themselves. But what if we allow any link anywhere? We get a general graph directory structure where directories can form cycles.
Imagine this: Directory A contains a link to Directory B, which contains a link to Directory C, which contains a link back to Directory A. You've created a loop. Now try traversing from A to find all files—you could walk forever: A → B → C → A → B → C...
The Real Danger: Garbage Collection
The bigger issue isn't infinite traversal (we can mark visited directories). It's garbage collection—reclaiming space from deleted files and directories.
Analogy: Think of a chain of people holding hands in a circle. If everyone lets go except for two people still holding each other's hands, they form an isolated island. From the outside, you can't reach them, but they still occupy space. In file systems, this is a self-contained cycle with no external references.
Normal reference counting fails here. If you delete the last external pointer to our A-B-C cycle, all three directories still have non-zero reference counts (they reference each other), so they won't be freed—even though they're unreachable garbage.
Solutions
File systems typically handle this by:
- Prohibiting cycles entirely (stay acyclic)
- Using garbage collection algorithms that detect unreachable cycles (expensive)
- Allowing only symbolic links to create potential cycles (they don't affect reference counts)
Key Takeaway: General graph directories with unrestricted hard links can create cycles that break simple reference counting, requiring expensive cycle-detection algorithms or design restrictions to prevent orphaned, unreachable storage.