Operating SystemsDirectory Structure

Directory Structure

LevelIntermediate

Duration75 mins

TopicDirectory Structure

4 / 5

Acyclic-Graph Directory

When One Path Isn't Enough

Consider a shared library file used by dozens of programs: /usr/lib/libc.so.6. In a pure tree, this file could only exist in one location. But what if you need the same library accessible from /lib64/libc.so.6 for compatibility? Copy the file? That wastes space and creates synchronization nightmares.\n\nThe solution is acyclic-graph directories—an extension of tree directories that allows a file (or directory) to have multiple parents. A single file can appear at multiple paths, enabling sharing without duplication. The 'acyclic' constraint ensures we don't create infinite loops when traversing the structure.\n\nThis structure is what enables hard links and symbolic links in UNIX systems. Understanding acyclic-graph directories reveals how file systems balance the flexibility of sharing with the need for consistent operations like deletion and traversal.

What You Will Master

By completing this page, you will understand how acyclic-graph directories extend trees for sharing, master hard links and symbolic links implementation, analyze reference counting for deletion, understand the critical importance of the acyclic constraint, and recognize the consistency challenges in graph-structured directories.

From Trees to Graphs

Trees have a fundamental limitation: each node has exactly one parent. This means:\n\n1. Each file has exactly one path from root\n2. No sharing without file duplication\n3. Containment is absolute—a file belongs to one directory\n\nAn acyclic-graph directory relaxes the single-parent constraint while preserving essential properties:\n\n\nTree Property (strict): Acyclic Graph Property:\nEach node has ONE parent → Each node can have MULTIPLE parents\nOne path to each node → Multiple paths to some nodes\nNo sharing possible → Sharing via links\n\n\nThe Critical Constraint: Acyclicity\n\nWhy "acyclic"? Consider what happens if we allowed cycles:\n\n\nCycle Example (FORBIDDEN):\n/home/alice/link → /home\n\nPath resolution for /home/alice/link/alice/link/alice/link/...\n→ Never terminates! Infinite loop!\n\n\nCycles would break path resolution, directory traversal, and recursive operations like rm -r. The acyclic constraint ensures:\n\n1. Path resolution always terminates\n2. Recursive traversals visit finite nodes\n3. No infinite loops in any algorithm\n\nFormal Definition:\n\nAn acyclic-graph directory is a Directed Acyclic Graph (DAG):\n\n\nG = (V, E)\n\nwhere:\n V = nodes (files and directories)\n E = directed edges (parent → child)\n ∄ cycle: v₁ → v₂ → ... → vₙ → v₁\n

Converting Mermaid diagram...

Key Observations from the Diagram:\n\n1. Shared Directory: The shared/ directory has TWO parents (alice and bob). Both users see it in their home.\n\n2. Shared File: libc.so.6 is reachable via /lib/libc.so.6 AND /usr/lib/libc.so.6. One physical file, two paths.\n\n3. No Cycles: Following edges always moves 'downward'—you can never return to an ancestor by following child links.\n\nTypes of Sharing:\n\n| Mechanism | What It Links | Creates | Example |\n|-----------|---------------|---------|---------|\n| Hard link | File to additional directory entry | Same inode, multiple names | ln file link |\n| Symbolic link | Path reference | New inode pointing to path string | ln -s /path/to/target link |\n| Directory hard link | (Usually prohibited) | - | Most systems disallow |\n\nWe'll explore each mechanism in depth in the following sections.

Why Prohibit Directory Hard Links?

Most UNIX systems prohibit hard links to directories (except for the implicit . and .. entries). Reason: It's too easy to create cycles accidentally. If alice/linkdir → /home creates a cycle, the file system is corrupted. Only root can sometimes create directory hard links, and it's generally avoided.

Hard Links

A hard link is a directory entry that points directly to a file's inode—the same inode another entry points to. The file has multiple names, but exists once on disk.\n\nHow Hard Links Work:\n\n\nInitial state after creating 'original.txt':\n\n/home/alice/original.txt → inode #12345 → [data blocks]\n (link count: 1)\n\nAfter: ln /home/alice/original.txt /home/bob/copy.txt\n\n/home/alice/original.txt → inode #12345 → [data blocks]\n/home/bob/copy.txt →↗ (link count: 2)\n\nBoth names point to the SAME inode. No data copied.\n\n\nKey Properties:\n\n1. Same inode: All hard links share inode number, thus same file metadata\n2. No "original": All links are equal; first created isn't special\n3. Same filesystem only: Hard links cannot cross filesystem boundaries\n4. Reference counted: File deleted only when link count reaches 0\n5. Transparent to applications: Programs can't tell they opened via a link

hard_links.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
 * Hard Links Demonstration
 * Shows how hard links work at the system call level.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
 
/*
 * Display file information including inode and link count
 */
void show_file_info(const char *path) {
    struct stat st;
    
    if (stat(path, &st) == -1) {
        printf("%s: %s\n", path, strerror(errno));
        return;
    }
    
    printf("%-30s  inode: %-10lu  links: %-2lu  size: %lu bytes\n",
           path, (unsigned long)st.st_ino, 
           (unsigned long)st.st_nlink, (unsigned long)st.st_size);
}
 
/*
 * Create a hard link with explanation
 */
void create_hard_link(const char *target, const char *link_name) {
    printf("\nCreating hard link: %s → %s\n", link_name, target);
    
    if (link(target, link_name) == -1) {
        printf("  ERROR: %s\n", strerror(errno));
        return;
    }
    
    printf("  Success!\n");
}
 
/*
 * Demonstrate hard link properties
 */
void demonstrate_hard_links(void) {
    printf("=== Hard Links Demonstration ===\n\n");
    
    const char *original = "/tmp/original.txt";
    const char *link1 = "/tmp/hardlink1.txt";
    const char *link2 = "/tmp/hardlink2.txt";
    
    /* Create original file */
    printf("Step 1: Create original file\n");
    int fd = open(original, O_CREAT | O_WRONLY | O_TRUNC, 0644);
    if (fd >= 0) {
        write(fd, "Hello, World!\n", 14);
        close(fd);
    }
    show_file_info(original);
    
    /* Create first hard link */
    printf("\nStep 2: Create first hard link\n");
    create_hard_link(original, link1);
    show_file_info(original);
    show_file_info(link1);
    
    /* Create second hard link */
    printf("\nStep 3: Create second hard link\n");
    create_hard_link(original, link2);
    show_file_info(original);
    show_file_info(link1);
    show_file_info(link2);
    
    printf("\n>>> Notice: All three have the SAME inode number!\n");
    printf(">>> Link count is now 3.\n");
    
    /* Modify through one link, visible through all */
    printf("\nStep 4: Modify through link1, read through link2\n");
    fd = open(link1, O_WRONLY | O_APPEND);
    if (fd >= 0) {
        write(fd, "Modified via link1\n", 19);
        close(fd);
    }
    printf("Written to: %s\n", link1);
    
    /* Read through different link */
    char buffer[100];
    fd = open(link2, O_RDONLY);
    if (fd >= 0) {
        ssize_t n = read(fd, buffer, sizeof(buffer) - 1);
        if (n > 0) {
            buffer[n] = '\0';
            printf("Read from %s:\n%s", link2, buffer);
        }
        close(fd);
    }
    
    printf("\n>>> Changes through any link affect the same file!\n");
    
    /* Delete original - other links still work */
    printf("\nStep 5: Delete 'original' file\n");
    unlink(original);
    printf("Deleted: %s\n", original);
    show_file_info(original);  /* Will show error */
    show_file_info(link1);
    show_file_info(link2);
    
    printf("\n>>> 'Original' is gone, but file still exists!\n");
    printf(">>> Link count is now 2. Data is NOT deleted.\n");
    
    /* File data deleted only when last link removed */
    printf("\nStep 6: Delete remaining links\n");
    unlink(link1);
    printf("Deleted: %s (link count now 1)\n", link1);
    show_file_info(link2);
    
    unlink(link2);
    printf("Deleted: %s (link count now 0 - FILE DELETED)\n", link2);
}
 
/*
 * Demonstrate hard link restrictions
 */
void demonstrate_restrictions(void) {
    printf("\n\n=== Hard Link Restrictions ===\n\n");
    
    /* Cannot link to directory (usually) */
    printf("Attempting to hard link a directory:\n");
    if (link("/tmp", "/tmp/link_to_tmp") == -1) {
        printf("  Failed: %s\n", strerror(errno));
        printf("  (Most systems prohibit directory hard links)\n");
    }
    
    /* Cannot cross filesystem boundaries */
    printf("\nCross-filesystem hard link would fail:\n");
    printf("  ln /home/file /mnt/usb/link\n");
    printf("  → ERROR: Invalid cross-device link\n");
    printf("  (Hard links require same inode table)\n");
}
 
int main() {
    demonstrate_hard_links();
    demonstrate_restrictions();
    
    return 0;
}

Reference Counting and Deletion:\n\nHard links use reference counting to manage file lifetime:\n\n\nInitial: link_count = 1\nAfter ln: link_count = 2\nAfter open(): (open_count++, but inode exists)\nAfter unlink #1: link_count = 1 (still exists)\nAfter unlink #2: link_count = 0\n IF open_count = 0 → DELETE file\n ELSE → DELETE when last close()\n\n\nThe unlink Semantic:\n\nThe unlink() system call:\n1. Removes the directory entry (the name)\n2. Decrements the inode's link count\n3. Does NOT delete file data unless link_count reaches 0 AND no processes have the file open\n\nThis allows:\n- Safe deletion while file is in use (data persists until closed)\n- Atomic replacement (unlink then create)\n- Temporary files that auto-delete on close

The /tmp Pattern

A common pattern for temporary files: create the file, open it, immediately unlink it. The file is now 'anonymous'—no path leads to it. When your process exits (or closes the file), the kernel automatically reclaims the space. No cleanup code needed!

Symbolic Links

A symbolic link (symlink) is a special file containing a text string interpreted as a path. Unlike hard links, symlinks are indirection—they point to a path, not an inode.\n\nHow Symbolic Links Work:\n\n\nCreating symlink: ln -s /usr/lib/libc.so.6 /lib/libc.so\n\n/lib/libc.so → inode #99999 (symlink)\n content: \"/usr/lib/libc.so.6\"\n \n/usr/lib/libc.so.6 → inode #12345 (regular file)\n [actual data]\n\nOpening /lib/libc.so:\n 1. Read inode #99999\n 2. See it's a symlink\n 3. Read symlink content: \"/usr/lib/libc.so.6\"\n 4. Resolve that path\n 5. Open inode #12345\n\n\nKey Differences from Hard Links:

Hard Links vs Symbolic Links
Property	Hard Link	Symbolic Link
Points to	Inode directly	Path string
Own inode?	No (shares target's)	Yes (separate inode)
Cross-filesystem	No	Yes
Link to directories	Usually prohibited	Allowed
Target deleted	Link still works	Becomes 'dangling'
Space overhead	Just directory entry	Inode + path string
Resolution	Direct	Requires path lookup

symbolic_links.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/*
 * Symbolic Links Demonstration
 * Shows symlink creation, resolution, and edge cases.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <limits.h>
 
/*
 * Display detailed info for file or symlink
 */
void show_link_info(const char *path) {
    struct stat st;
    char target[PATH_MAX];
    ssize_t len;
    
    /* lstat: get info about link itself, not target */
    if (lstat(path, &st) == -1) {
        printf("%s: %s\n", path, strerror(errno));
        return;
    }
    
    printf("%-30s  ", path);
    
    if (S_ISLNK(st.st_mode)) {
        /* Read symlink target */
        len = readlink(path, target, sizeof(target) - 1);
        if (len != -1) {
            target[len] = '\0';
            printf("[SYMLINK] → %s", target);
            
            /* Check if target exists */
            if (access(path, F_OK) == -1) {
                printf(" (DANGLING!)");
            }
        }
    } else if (S_ISREG(st.st_mode)) {
        printf("[FILE] inode: %lu, links: %lu", 
               (unsigned long)st.st_ino, (unsigned long)st.st_nlink);
    } else if (S_ISDIR(st.st_mode)) {
        printf("[DIR]");
    }
    
    printf("\n");
}
 
/*
 * Demonstrate symlink creation and resolution
 */
void demonstrate_symlinks(void) {
    printf("=== Symbolic Links Demonstration ===\n\n");
    
    const char *target = "/tmp/target_file.txt";
    const char *symlink_path = "/tmp/my_symlink";
    const char *relative_link = "/tmp/relative_link";
    
    /* Create target file */
    printf("Step 1: Create target file\n");
    int fd = open(target, O_CREAT | O_WRONLY, 0644);
    if (fd >= 0) {
        write(fd, "Original content\n", 17);
        close(fd);
    }
    show_link_info(target);
    
    /* Create absolute symlink */
    printf("\nStep 2: Create absolute symlink\n");
    if (symlink(target, symlink_path) == 0) {
        printf("Created: %s → %s\n", symlink_path, target);
    }
    show_link_info(symlink_path);
    
    /* Create relative symlink */
    printf("\nStep 3: Create relative symlink\n");
    if (symlink("target_file.txt", relative_link) == 0) {
        printf("Created: %s → target_file.txt (relative)\n", relative_link);
    }
    show_link_info(relative_link);
    
    /* Access through symlink */
    printf("\nStep 4: Access file through symlink\n");
    char buffer[100];
    fd = open(symlink_path, O_RDONLY);
    if (fd >= 0) {
        ssize_t n = read(fd, buffer, sizeof(buffer) - 1);
        if (n > 0) {
            buffer[n] = '\0';
            printf("Read via symlink: %s", buffer);
        }
        close(fd);
    }
    
    /* stat vs lstat */
    printf("\nStep 5: stat() vs lstat() difference\n");
    struct stat st;
    
    stat(symlink_path, &st);  /* Follows symlink */
    printf("stat(%s):  inode %lu (TARGET'S inode)\n", 
           symlink_path, (unsigned long)st.st_ino);
    
    lstat(symlink_path, &st);  /* Link itself */
    printf("lstat(%s): inode %lu (SYMLINK'S inode)\n", 
           symlink_path, (unsigned long)st.st_ino);
    
    /* Delete target - dangling link */
    printf("\nStep 6: Delete target - symlink becomes dangling\n");
    unlink(target);
    show_link_info(target);
    show_link_info(symlink_path);
    
    printf("\n>>> Symlink still exists but points to nothing!\n");
    printf(">>> Opening it will fail with ENOENT.\n");
    
    fd = open(symlink_path, O_RDONLY);
    if (fd == -1) {
        printf("open(%s): %s\n", symlink_path, strerror(errno));
    }
    
    /* Cleanup */
    unlink(symlink_path);
    unlink(relative_link);
}
 
/*
 * Demonstrate symlink to directory
 */
void demonstrate_directory_symlinks(void) {
    printf("\n\n=== Directory Symlinks ===\n\n");
    
    /* Create directory structure */
    mkdir("/tmp/real_dir", 0755);
    creat("/tmp/real_dir/file.txt", 0644);
    
    /* Create symlink to directory */
    printf("Creating symlink to directory:\n");
    if (symlink("/tmp/real_dir", "/tmp/dir_link") == 0) {
        printf("  /tmp/dir_link → /tmp/real_dir\n");
    }
    
    /* Access file through directory symlink */
    printf("\nAccessing file via directory symlink:\n");
    show_link_info("/tmp/dir_link/file.txt");
    
    /* cd into symlink */
    printf("\nThe path /tmp/dir_link/file.txt works!\n");
    printf("The symlink transparently redirects to /tmp/real_dir/\n");
    
    /* Cleanup */
    unlink("/tmp/real_dir/file.txt");
    rmdir("/tmp/real_dir");
    unlink("/tmp/dir_link");
}
 
/*
 * Demonstrate symlink loops (avoided by kernel)
 */
void demonstrate_loop_protection(void) {
    printf("\n\n=== Symlink Loop Protection ===\n\n");
    
    /* Create circular symlinks */
    symlink("/tmp/link_b", "/tmp/link_a");
    symlink("/tmp/link_a", "/tmp/link_b");
    
    printf("Created circular symlinks:\n");
    printf("  /tmp/link_a → /tmp/link_b\n");
    printf("  /tmp/link_b → /tmp/link_a\n\n");
    
    /* Try to open - kernel detects loop */
    printf("Attempting to open /tmp/link_a:\n");
    int fd = open("/tmp/link_a", O_RDONLY);
    if (fd == -1) {
        printf("  Failed: %s\n", strerror(errno));
        printf("  (ELOOP: Too many symbolic links)\n");
    }
    
    printf("\n>>> Kernel counted symlink traversals and stopped!\n");
    printf(">>> Typical limit: 40 symlink traversals (SYMLOOP_MAX).\n");
    
    /* Cleanup */
    unlink("/tmp/link_a");
    unlink("/tmp/link_b");
}
 
int main() {
    demonstrate_symlinks();
    demonstrate_directory_symlinks();
    demonstrate_loop_protection();
    
    return 0;
}

Absolute vs Relative Symlinks:\n\n| Type | Example | When Target Moves |\n|------|---------|-------------------|\n| Absolute | /lib/libc → /usr/lib/libc.so.6 | Breaks if moved to different tree |\n| Relative | lib/libc → ../usr/lib/libc.so.6 | Works if relative positions preserved |\n\nRelative symlinks are often preferred for software packages, allowing entire directory trees to be relocated.\n\nThe Dangling Link Problem:\n\nUnlike hard links (which prevent target deletion), symlinks can become 'dangling'—pointing to non-existent targets:\n\n\n$ ln -s /tmp/important important_link\n$ rm /tmp/important\n$ cat important_link\ncat: important_link: No such file or directory\n\n\nThis is by design—symlinks are 'weak references' that don't prevent deletion.

Symlink Security Concerns

Symlinks can be security risks. A malicious user might create /tmp/symlink → /etc/passwd, tricking privileged programs into modifying sensitive files. The O_NOFOLLOW flag and careful path validation are essential for security-sensitive code.

The Acyclic Constraint

The 'acyclic' part of acyclic-graph directories is crucial. Cycles break fundamental file system operations.\n\nWhy Cycles Are Dangerous:\n\n1. Infinite Path Resolution\n\n\nIf: /a/b/link → /a\n\nResolving: /a/b/link/b/link/b/link/...\n→ Never terminates!\n→ System hangs or crashes\n\n\n2. Recursive Operations\n\n\nrm -r /a (with cycle /a/b/link → /a)\n\n→ rm deletes /a/b/link → tries to delete /a → /a/b/link → /a ...\n→ Infinite loop or inconsistent state\n\n\n3. Traversal/Find Operations\n\n\nfind /a -name '*.txt'\n\n→ With cycles, same directories revisited infinitely\n\n\nHow Systems Prevent Cycles:\n\n| Mechanism | Applied To | Effect |\n|-----------|------------|--------|\n| Prohibit directory hard links | Hard links | Cannot create cycles directly |\n| Symlink loop detection | Path resolution | Kernel counts traversals, errors at limit |\n| Mount point checks | Mounts | Prevent mounting tree inside itself |

cycle_detection.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
 * Cycle Detection and Prevention
 * Demonstrates why cycles are dangerous and how systems prevent them.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <sys/stat.h>
#include <limits.h>
 
/*
 * Attempt to create directory hard link (usually fails)
 * This is the primary cycle prevention mechanism.
 */
void try_directory_hardlink(void) {
    printf("=== Attempting Directory Hard Link ===\n\n");
    
    mkdir("/tmp/cycle_test", 0755);
    
    printf("Trying: link(/tmp/cycle_test, /tmp/cycle_test/self)\n");
    
    if (link("/tmp/cycle_test", "/tmp/cycle_test/self") == -1) {
        printf("Failed: %s\n\n", strerror(errno));
        printf(">>> EPERM: Most systems prohibit directory hard links!\n");
        printf(">>> This is PRIMARY cycle prevention.\n");
    } else {
        printf("Success (unusual - check your system!)\n");
        unlink("/tmp/cycle_test/self");
    }
    
    rmdir("/tmp/cycle_test");
}
 
/*
 * Demonstrate symlink loop detection (ELOOP)
 */
void demonstrate_symloop(void) {
    printf("\n\n=== Symlink Loop Detection ===\n\n");
    
    mkdir("/tmp/loop_test", 0755);
    
    /* Create chain of symlinks */
    printf("Creating chain: a → b → c → d → e → a\n");
    symlink("/tmp/loop_test/b", "/tmp/loop_test/a");
    symlink("/tmp/loop_test/c", "/tmp/loop_test/b");
    symlink("/tmp/loop_test/d", "/tmp/loop_test/c");
    symlink("/tmp/loop_test/e", "/tmp/loop_test/d");
    symlink("/tmp/loop_test/a", "/tmp/loop_test/e");  /* Completes cycle */
    
    /* Try to access */
    printf("\nAttempting to open /tmp/loop_test/a:\n");
    int fd = open("/tmp/loop_test/a/file", O_RDONLY);
    if (fd == -1 && errno == ELOOP) {
        printf("  Error: ELOOP (too many symbolic links)\n\n");
        printf(">>> Kernel detected the cycle!\n");
        printf(">>> Resolution stopped after ~40 symlink traversals.\n");
    }
    
    /* Show how find handles cycles */
    printf("\nThe 'find' command would detect similar cycles via inode tracking.\n");
    
    /* Cleanup */
    unlink("/tmp/loop_test/a");
    unlink("/tmp/loop_test/b");
    unlink("/tmp/loop_test/c");
    unlink("/tmp/loop_test/d");
    unlink("/tmp/loop_test/e");
    rmdir("/tmp/loop_test");
}
 
/*
 * Simulate safe recursive traversal with cycle detection
 */
#define MAX_VISITED 100
 
typedef struct {
    dev_t dev;
    ino_t ino;
} InodeRef;
 
typedef struct {
    InodeRef visited[MAX_VISITED];
    int count;
} VisitedSet;
 
int already_visited(VisitedSet *set, dev_t dev, ino_t ino) {
    for (int i = 0; i < set->count; i++) {
        if (set->visited[i].dev == dev && set->visited[i].ino == ino) {
            return 1;  /* Already visited! Cycle detected */
        }
    }
    return 0;
}
 
void mark_visited(VisitedSet *set, dev_t dev, ino_t ino) {
    if (set->count < MAX_VISITED) {
        set->visited[set->count].dev = dev;
        set->visited[set->count].ino = ino;
        set->count++;
    }
}
 
/*
 * Safe directory traversal with cycle detection
 */
void safe_traverse(const char *path, int depth, VisitedSet *visited) {
    struct stat st;
    
    if (lstat(path, &st) == -1) return;
    if (!S_ISDIR(st.st_mode)) return;
    
    /* Check for cycle */
    if (already_visited(visited, st.st_dev, st.st_ino)) {
        printf("%*s[CYCLE DETECTED: already visited inode %lu]\n", 
               depth * 2, "", (unsigned long)st.st_ino);
        return;
    }
    
    mark_visited(visited, st.st_dev, st.st_ino);
    
    /* Print current directory */
    for (int i = 0; i < depth; i++) printf("  ");
    printf("📂 %s (inode %lu)\n", path, (unsigned long)st.st_ino);
    
    /* Traverse contents... (simplified) */
}
 
void demonstrate_safe_traversal(void) {
    printf("\n\n=== Safe Recursive Traversal ===\n\n");
    
    printf("To safely traverse directories with potential cycles:\n\n");
    printf("1. Track visited (dev, inode) pairs\n");
    printf("2. Before descending, check if already visited\n");
    printf("3. If visited, skip (cycle!) otherwise add to set\n\n");
    
    printf("This is how 'find', 'du', and 'tar' handle cycles.\n");
    printf("The -xdev flag prevents crossing filesystems (different dev_t).\n");
}
 
int main() {
    try_directory_hardlink();
    demonstrate_symloop();
    demonstrate_safe_traversal();
    
    return 0;
}

The Linux Symlink Limit (SYMLOOP_MAX):\n\nLinux limits symlink traversals during path resolution:\n\n\nTotal symlinks in path: max 40 (typical)\nConsecutive symlinks: varies by kernel version\n\nExceeding limit → ELOOP error\n\n\nThis prevents denial-of-service and infinite loops while allowing legitimate symlink chains.\n\nPOSIX Requirements:\n\nPOSIX specifies:\n- SYMLOOP_MAX: Minimum 8 (Linux typically uses 40)\n- Path resolution must fail with ELOOP if limit exceeded\n- Implementations may use higher limits

The . and .. Paradox

Every directory has '.' (self) and '..' (parent) entries—these ARE directory hard links! How does this not create cycles? The key insight: '.' and '..' are special cases managed by the kernel, not user-creatable hard links. The kernel ensures these never create actual cycles in the graph structure.

Consistency Challenges

Acyclic-graph directories introduce consistency challenges not present in pure trees. When a file has multiple paths, coordinating operations becomes complex.\n\nChallenge 1: Multiple Name Problem\n\nWith hard links, a file has multiple names\n\n\n/home/alice/data.csv\n/home/bob/data.csv\n/archive/old_data.csv\n\n\nAll three paths refer to the same file. Questions arise:\n- Who 'owns' the file?\n- Which path should ls -la report?\n- If Alice deletes 'her' copy, Bob's still works... is this expected?\n\nChallenge 2: Directory Parent Ambiguity (if allowed)\n\nIf directory hard links were allowed:\n\n\n/home/shared/ has parents: /home/alice/, /home/bob/\n\nWhat is the result of:\n cd /home/shared\n cd .. ← Goes to alice/ or bob/?\n pwd ← Shows which path?\n\n\nMost systems answer by:\n- Forbidding directory hard links (sidestepping the problem)\n- Storing the entry path at cd time and using it for ..\n\nChallenge 3: Disk Space Accounting\n\nWithhard-linked files:\n\n\n/home/alice/big.dat (hard linked)\n/home/bob/big.dat\n\nFile size: 1 GB\n\nDisk usage:\n Total space used: 1 GB (only one copy exists)\n alice quota used: ??? \n bob quota used: ???\n\n\nDifferent systems handle this differently:\n- Count against first link's owner\n- Count against all linked owners (problematic)\n- Attribute to inode owner, not directory location

Consistency Challenges and Solutions
Challenge	Tree Behavior	Graph Behavior	Typical Solution
File deletion	One unlink removes file	Must track link count	Reference counting
Ownership	Owner clear from path	Multiple 'locations'	inode stores owner
Quota accounting	Simple directory based	Shared files complex	Charge inode owner
Traversal	Each node visited once	Might revisit shared nodes	Track visited inodes
Backup/copy	Simple tree walk	Avoid duplicating shared	Detect shared inodes

Challenge 4: Backup and Archive Integrity\n\nWhen backing up a directory tree with hard links:\n\n\n$ tar czf backup.tar.gz /home\n\n\nShould the archive:\n- Store the file once, preserving link relationships? ✓ (tar -h behavior)\n- Store multiple copies? (wastes space, loses relationship)\n\nMost tools detect hard links by tracking inodes and store data once with multiple directory entries.\n\nChallenge 5: Symbolic Link Resolution Timing\n\nSymlinks are resolved at access time, not creation time:\n\n\n$ ln -s config.prod config\n$ cat config # Reads config.prod\n\n$ rm config.prod\n$ ln -s config.dev config.prod # Replace target\n$ cat config # Now reads config.dev's content!\n\n\nThis is powerful (late binding) but can confuse programs expecting stable targets.

TOCTTOU Vulnerabilities

Time-Of-Check-To-Time-Of-Use: A symlink can change between when you check it and when you use it. Evil attackers exploit this: 'if target is safe file, open target' → attacker swaps symlink after check → program opens /etc/passwd. Use O_NOFOLLOW and careful coding!

Summary: Acyclic-Graph Directory Fundamentals

We've explored acyclic-graph directories—the extension of tree structures that enables file sharing through links. This powerful capability comes with complexity that file systems must carefully manage.

Key Takeaways

•Graphs extend trees for sharing — By allowing nodes to have multiple parents, files can be accessed via multiple paths without duplication. This is implemented through hard and symbolic links.
•Hard links share inodes — Multiple directory entries point to the same inode. All links are equal; the file is deleted when the last link is removed (reference counting).
•Symbolic links are path references — Symlinks contain path strings resolved at access time. They can cross filesystems and link to directories, but can become dangling.
•The acyclic constraint is critical — Cycles would break path resolution and recursive operations. Systems prevent them by prohibiting directory hard links and detecting symlink loops.
•Consistency requires careful design — Multiple paths to files complicate ownership, quotas, backups, and traversal. Reference counting and inode tracking address these challenges.
•Security implications exist — Symlinks can be attack vectors (TOCTTOU, privilege escalation). Careful validation and O_NOFOLLOW are essential.

Page Complete

You now understand how acyclic-graph directories enable file sharing while maintaining the essential properties needed for correct file system operation. Hard links and symbolic links are fundamental UNIX concepts you'll encounter constantly. Next, we'll explore general graph directories—what happens when cycles are allowed, and how some advanced systems handle this.

What's Next:\n\nIn the final page of this module, we'll explore general graph directories—structures that allow or must handle cycles. We'll examine garbage collection approaches, historical systems that experimented with cycles, and why acyclic remains the dominant design despite theoretical expressiveness of general graphs.

4 / 5

Loading learning content...

Operating SystemsDirectory Structure

Directory Structure

LevelIntermediate

Duration75 mins

TopicDirectory Structure

4 / 5

Acyclic-Graph Directory

When One Path Isn't Enough

What You Will Master

From Trees to Graphs

Converting Mermaid diagram...

Why Prohibit Directory Hard Links?

Hard Links

hard_links.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
 * Hard Links Demonstration
 * Shows how hard links work at the system call level.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
 
/*
 * Display file information including inode and link count
 */
void show_file_info(const char *path) {
    struct stat st;
    
    if (stat(path, &st) == -1) {
        printf("%s: %s\n", path, strerror(errno));
        return;
    }
    
    printf("%-30s  inode: %-10lu  links: %-2lu  size: %lu bytes\n",
           path, (unsigned long)st.st_ino, 
           (unsigned long)st.st_nlink, (unsigned long)st.st_size);
}
 
/*
 * Create a hard link with explanation
 */
void create_hard_link(const char *target, const char *link_name) {
    printf("\nCreating hard link: %s → %s\n", link_name, target);
    
    if (link(target, link_name) == -1) {
        printf("  ERROR: %s\n", strerror(errno));
        return;
    }
    
    printf("  Success!\n");
}
 
/*
 * Demonstrate hard link properties
 */
void demonstrate_hard_links(void) {
    printf("=== Hard Links Demonstration ===\n\n");
    
    const char *original = "/tmp/original.txt";
    const char *link1 = "/tmp/hardlink1.txt";
    const char *link2 = "/tmp/hardlink2.txt";
    
    /* Create original file */
    printf("Step 1: Create original file\n");
    int fd = open(original, O_CREAT | O_WRONLY | O_TRUNC, 0644);
    if (fd >= 0) {
        write(fd, "Hello, World!\n", 14);
        close(fd);
    }
    show_file_info(original);
    
    /* Create first hard link */
    printf("\nStep 2: Create first hard link\n");
    create_hard_link(original, link1);
    show_file_info(original);
    show_file_info(link1);
    
    /* Create second hard link */
    printf("\nStep 3: Create second hard link\n");
    create_hard_link(original, link2);
    show_file_info(original);
    show_file_info(link1);
    show_file_info(link2);
    
    printf("\n>>> Notice: All three have the SAME inode number!\n");
    printf(">>> Link count is now 3.\n");
    
    /* Modify through one link, visible through all */
    printf("\nStep 4: Modify through link1, read through link2\n");
    fd = open(link1, O_WRONLY | O_APPEND);
    if (fd >= 0) {
        write(fd, "Modified via link1\n", 19);
        close(fd);
    }
    printf("Written to: %s\n", link1);
    
    /* Read through different link */
    char buffer[100];
    fd = open(link2, O_RDONLY);
    if (fd >= 0) {
        ssize_t n = read(fd, buffer, sizeof(buffer) - 1);
        if (n > 0) {
            buffer[n] = '\0';
            printf("Read from %s:\n%s", link2, buffer);
        }
        close(fd);
    }
    
    printf("\n>>> Changes through any link affect the same file!\n");
    
    /* Delete original - other links still work */
    printf("\nStep 5: Delete 'original' file\n");
    unlink(original);
    printf("Deleted: %s\n", original);
    show_file_info(original);  /* Will show error */
    show_file_info(link1);
    show_file_info(link2);
    
    printf("\n>>> 'Original' is gone, but file still exists!\n");
    printf(">>> Link count is now 2. Data is NOT deleted.\n");
    
    /* File data deleted only when last link removed */
    printf("\nStep 6: Delete remaining links\n");
    unlink(link1);
    printf("Deleted: %s (link count now 1)\n", link1);
    show_file_info(link2);
    
    unlink(link2);
    printf("Deleted: %s (link count now 0 - FILE DELETED)\n", link2);
}
 
/*
 * Demonstrate hard link restrictions
 */
void demonstrate_restrictions(void) {
    printf("\n\n=== Hard Link Restrictions ===\n\n");
    
    /* Cannot link to directory (usually) */
    printf("Attempting to hard link a directory:\n");
    if (link("/tmp", "/tmp/link_to_tmp") == -1) {
        printf("  Failed: %s\n", strerror(errno));
        printf("  (Most systems prohibit directory hard links)\n");
    }
    
    /* Cannot cross filesystem boundaries */
    printf("\nCross-filesystem hard link would fail:\n");
    printf("  ln /home/file /mnt/usb/link\n");
    printf("  → ERROR: Invalid cross-device link\n");
    printf("  (Hard links require same inode table)\n");
}
 
int main() {
    demonstrate_hard_links();
    demonstrate_restrictions();
    
    return 0;
}

The /tmp Pattern

Symbolic Links

Hard Links vs Symbolic Links
Property	Hard Link	Symbolic Link
Points to	Inode directly	Path string
Own inode?	No (shares target's)	Yes (separate inode)
Cross-filesystem	No	Yes
Link to directories	Usually prohibited	Allowed
Target deleted	Link still works	Becomes 'dangling'
Space overhead	Just directory entry	Inode + path string
Resolution	Direct	Requires path lookup

symbolic_links.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/*
 * Symbolic Links Demonstration
 * Shows symlink creation, resolution, and edge cases.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <limits.h>
 
/*
 * Display detailed info for file or symlink
 */
void show_link_info(const char *path) {
    struct stat st;
    char target[PATH_MAX];
    ssize_t len;
    
    /* lstat: get info about link itself, not target */
    if (lstat(path, &st) == -1) {
        printf("%s: %s\n", path, strerror(errno));
        return;
    }
    
    printf("%-30s  ", path);
    
    if (S_ISLNK(st.st_mode)) {
        /* Read symlink target */
        len = readlink(path, target, sizeof(target) - 1);
        if (len != -1) {
            target[len] = '\0';
            printf("[SYMLINK] → %s", target);
            
            /* Check if target exists */
            if (access(path, F_OK) == -1) {
                printf(" (DANGLING!)");
            }
        }
    } else if (S_ISREG(st.st_mode)) {
        printf("[FILE] inode: %lu, links: %lu", 
               (unsigned long)st.st_ino, (unsigned long)st.st_nlink);
    } else if (S_ISDIR(st.st_mode)) {
        printf("[DIR]");
    }
    
    printf("\n");
}
 
/*
 * Demonstrate symlink creation and resolution
 */
void demonstrate_symlinks(void) {
    printf("=== Symbolic Links Demonstration ===\n\n");
    
    const char *target = "/tmp/target_file.txt";
    const char *symlink_path = "/tmp/my_symlink";
    const char *relative_link = "/tmp/relative_link";
    
    /* Create target file */
    printf("Step 1: Create target file\n");
    int fd = open(target, O_CREAT | O_WRONLY, 0644);
    if (fd >= 0) {
        write(fd, "Original content\n", 17);
        close(fd);
    }
    show_link_info(target);
    
    /* Create absolute symlink */
    printf("\nStep 2: Create absolute symlink\n");
    if (symlink(target, symlink_path) == 0) {
        printf("Created: %s → %s\n", symlink_path, target);
    }
    show_link_info(symlink_path);
    
    /* Create relative symlink */
    printf("\nStep 3: Create relative symlink\n");
    if (symlink("target_file.txt", relative_link) == 0) {
        printf("Created: %s → target_file.txt (relative)\n", relative_link);
    }
    show_link_info(relative_link);
    
    /* Access through symlink */
    printf("\nStep 4: Access file through symlink\n");
    char buffer[100];
    fd = open(symlink_path, O_RDONLY);
    if (fd >= 0) {
        ssize_t n = read(fd, buffer, sizeof(buffer) - 1);
        if (n > 0) {
            buffer[n] = '\0';
            printf("Read via symlink: %s", buffer);
        }
        close(fd);
    }
    
    /* stat vs lstat */
    printf("\nStep 5: stat() vs lstat() difference\n");
    struct stat st;
    
    stat(symlink_path, &st);  /* Follows symlink */
    printf("stat(%s):  inode %lu (TARGET'S inode)\n", 
           symlink_path, (unsigned long)st.st_ino);
    
    lstat(symlink_path, &st);  /* Link itself */
    printf("lstat(%s): inode %lu (SYMLINK'S inode)\n", 
           symlink_path, (unsigned long)st.st_ino);
    
    /* Delete target - dangling link */
    printf("\nStep 6: Delete target - symlink becomes dangling\n");
    unlink(target);
    show_link_info(target);
    show_link_info(symlink_path);
    
    printf("\n>>> Symlink still exists but points to nothing!\n");
    printf(">>> Opening it will fail with ENOENT.\n");
    
    fd = open(symlink_path, O_RDONLY);
    if (fd == -1) {
        printf("open(%s): %s\n", symlink_path, strerror(errno));
    }
    
    /* Cleanup */
    unlink(symlink_path);
    unlink(relative_link);
}
 
/*
 * Demonstrate symlink to directory
 */
void demonstrate_directory_symlinks(void) {
    printf("\n\n=== Directory Symlinks ===\n\n");
    
    /* Create directory structure */
    mkdir("/tmp/real_dir", 0755);
    creat("/tmp/real_dir/file.txt", 0644);
    
    /* Create symlink to directory */
    printf("Creating symlink to directory:\n");
    if (symlink("/tmp/real_dir", "/tmp/dir_link") == 0) {
        printf("  /tmp/dir_link → /tmp/real_dir\n");
    }
    
    /* Access file through directory symlink */
    printf("\nAccessing file via directory symlink:\n");
    show_link_info("/tmp/dir_link/file.txt");
    
    /* cd into symlink */
    printf("\nThe path /tmp/dir_link/file.txt works!\n");
    printf("The symlink transparently redirects to /tmp/real_dir/\n");
    
    /* Cleanup */
    unlink("/tmp/real_dir/file.txt");
    rmdir("/tmp/real_dir");
    unlink("/tmp/dir_link");
}
 
/*
 * Demonstrate symlink loops (avoided by kernel)
 */
void demonstrate_loop_protection(void) {
    printf("\n\n=== Symlink Loop Protection ===\n\n");
    
    /* Create circular symlinks */
    symlink("/tmp/link_b", "/tmp/link_a");
    symlink("/tmp/link_a", "/tmp/link_b");
    
    printf("Created circular symlinks:\n");
    printf("  /tmp/link_a → /tmp/link_b\n");
    printf("  /tmp/link_b → /tmp/link_a\n\n");
    
    /* Try to open - kernel detects loop */
    printf("Attempting to open /tmp/link_a:\n");
    int fd = open("/tmp/link_a", O_RDONLY);
    if (fd == -1) {
        printf("  Failed: %s\n", strerror(errno));
        printf("  (ELOOP: Too many symbolic links)\n");
    }
    
    printf("\n>>> Kernel counted symlink traversals and stopped!\n");
    printf(">>> Typical limit: 40 symlink traversals (SYMLOOP_MAX).\n");
    
    /* Cleanup */
    unlink("/tmp/link_a");
    unlink("/tmp/link_b");
}
 
int main() {
    demonstrate_symlinks();
    demonstrate_directory_symlinks();
    demonstrate_loop_protection();
    
    return 0;
}

Symlink Security Concerns

The Acyclic Constraint

cycle_detection.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
 * Cycle Detection and Prevention
 * Demonstrates why cycles are dangerous and how systems prevent them.
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include <sys/stat.h>
#include <limits.h>
 
/*
 * Attempt to create directory hard link (usually fails)
 * This is the primary cycle prevention mechanism.
 */
void try_directory_hardlink(void) {
    printf("=== Attempting Directory Hard Link ===\n\n");
    
    mkdir("/tmp/cycle_test", 0755);
    
    printf("Trying: link(/tmp/cycle_test, /tmp/cycle_test/self)\n");
    
    if (link("/tmp/cycle_test", "/tmp/cycle_test/self") == -1) {
        printf("Failed: %s\n\n", strerror(errno));
        printf(">>> EPERM: Most systems prohibit directory hard links!\n");
        printf(">>> This is PRIMARY cycle prevention.\n");
    } else {
        printf("Success (unusual - check your system!)\n");
        unlink("/tmp/cycle_test/self");
    }
    
    rmdir("/tmp/cycle_test");
}
 
/*
 * Demonstrate symlink loop detection (ELOOP)
 */
void demonstrate_symloop(void) {
    printf("\n\n=== Symlink Loop Detection ===\n\n");
    
    mkdir("/tmp/loop_test", 0755);
    
    /* Create chain of symlinks */
    printf("Creating chain: a → b → c → d → e → a\n");
    symlink("/tmp/loop_test/b", "/tmp/loop_test/a");
    symlink("/tmp/loop_test/c", "/tmp/loop_test/b");
    symlink("/tmp/loop_test/d", "/tmp/loop_test/c");
    symlink("/tmp/loop_test/e", "/tmp/loop_test/d");
    symlink("/tmp/loop_test/a", "/tmp/loop_test/e");  /* Completes cycle */
    
    /* Try to access */
    printf("\nAttempting to open /tmp/loop_test/a:\n");
    int fd = open("/tmp/loop_test/a/file", O_RDONLY);
    if (fd == -1 && errno == ELOOP) {
        printf("  Error: ELOOP (too many symbolic links)\n\n");
        printf(">>> Kernel detected the cycle!\n");
        printf(">>> Resolution stopped after ~40 symlink traversals.\n");
    }
    
    /* Show how find handles cycles */
    printf("\nThe 'find' command would detect similar cycles via inode tracking.\n");
    
    /* Cleanup */
    unlink("/tmp/loop_test/a");
    unlink("/tmp/loop_test/b");
    unlink("/tmp/loop_test/c");
    unlink("/tmp/loop_test/d");
    unlink("/tmp/loop_test/e");
    rmdir("/tmp/loop_test");
}
 
/*
 * Simulate safe recursive traversal with cycle detection
 */
#define MAX_VISITED 100
 
typedef struct {
    dev_t dev;
    ino_t ino;
} InodeRef;
 
typedef struct {
    InodeRef visited[MAX_VISITED];
    int count;
} VisitedSet;
 
int already_visited(VisitedSet *set, dev_t dev, ino_t ino) {
    for (int i = 0; i < set->count; i++) {
        if (set->visited[i].dev == dev && set->visited[i].ino == ino) {
            return 1;  /* Already visited! Cycle detected */
        }
    }
    return 0;
}
 
void mark_visited(VisitedSet *set, dev_t dev, ino_t ino) {
    if (set->count < MAX_VISITED) {
        set->visited[set->count].dev = dev;
        set->visited[set->count].ino = ino;
        set->count++;
    }
}
 
/*
 * Safe directory traversal with cycle detection
 */
void safe_traverse(const char *path, int depth, VisitedSet *visited) {
    struct stat st;
    
    if (lstat(path, &st) == -1) return;
    if (!S_ISDIR(st.st_mode)) return;
    
    /* Check for cycle */
    if (already_visited(visited, st.st_dev, st.st_ino)) {
        printf("%*s[CYCLE DETECTED: already visited inode %lu]\n", 
               depth * 2, "", (unsigned long)st.st_ino);
        return;
    }
    
    mark_visited(visited, st.st_dev, st.st_ino);
    
    /* Print current directory */
    for (int i = 0; i < depth; i++) printf("  ");
    printf("📂 %s (inode %lu)\n", path, (unsigned long)st.st_ino);
    
    /* Traverse contents... (simplified) */
}
 
void demonstrate_safe_traversal(void) {
    printf("\n\n=== Safe Recursive Traversal ===\n\n");
    
    printf("To safely traverse directories with potential cycles:\n\n");
    printf("1. Track visited (dev, inode) pairs\n");
    printf("2. Before descending, check if already visited\n");
    printf("3. If visited, skip (cycle!) otherwise add to set\n\n");
    
    printf("This is how 'find', 'du', and 'tar' handle cycles.\n");
    printf("The -xdev flag prevents crossing filesystems (different dev_t).\n");
}
 
int main() {
    try_directory_hardlink();
    demonstrate_symloop();
    demonstrate_safe_traversal();
    
    return 0;
}

The . and .. Paradox

Consistency Challenges

Consistency Challenges and Solutions
Challenge	Tree Behavior	Graph Behavior	Typical Solution
File deletion	One unlink removes file	Must track link count	Reference counting
Ownership	Owner clear from path	Multiple 'locations'	inode stores owner
Quota accounting	Simple directory based	Shared files complex	Charge inode owner
Traversal	Each node visited once	Might revisit shared nodes	Track visited inodes
Backup/copy	Simple tree walk	Avoid duplicating shared	Detect shared inodes

TOCTTOU Vulnerabilities

Summary: Acyclic-Graph Directory Fundamentals

Key Takeaways

•Graphs extend trees for sharing — By allowing nodes to have multiple parents, files can be accessed via multiple paths without duplication. This is implemented through hard and symbolic links.
•Hard links share inodes — Multiple directory entries point to the same inode. All links are equal; the file is deleted when the last link is removed (reference counting).
•Symbolic links are path references — Symlinks contain path strings resolved at access time. They can cross filesystems and link to directories, but can become dangling.
•The acyclic constraint is critical — Cycles would break path resolution and recursive operations. Systems prevent them by prohibiting directory hard links and detecting symlink loops.
•Consistency requires careful design — Multiple paths to files complicate ownership, quotas, backups, and traversal. Reference counting and inode tracking address these challenges.
•Security implications exist — Symlinks can be attack vectors (TOCTTOU, privilege escalation). Careful validation and O_NOFOLLOW are essential.

Page Complete

4 / 5