Chapter 34 of 38

Directory Structure

A typical laptop holds hundreds of thousands of files. Without some way to group and name them, finding your resume would mean scrolling through a single list containing every system library, photo and browser cache file on the machine.

Directories (folders) solve this. They give files names, group related files, and let many users and programs share one disk without stepping on each other.

A directory is a special file that maps file names to the files themselves. On UNIX-like systems, each directory entry maps a name to an inode number; the directory structure is the way these directories are organised and linked together.

In File Systems we learned that the inode holds everything about a file except its name, and in File Allocation Methods we saw how the inode finds the file's blocks. This chapter fills the last gap: how the OS goes from a name like /home/riya/notes.txt to an inode, and how directories are arranged.


What Is Inside a Directory?

A directory is just a file whose contents are a list of entries. In a UNIX file system, each entry is basically:

Directory "proj" (itself inode 50776)
+----------------+---------+
| name           | inode # |
+----------------+---------+
| .              | 50776   |  ← this directory itself
| ..             | 50757   |  ← parent directory
| readme.txt     | 50777   |
| src            | 50784   |
| docs           | 50796   |
| tests          | 50810   |
+----------------+---------+

That is all. The name lives here, and everything else (size, owner, permissions, block locations) lives in the inode. Some systems, such as FAT, store attributes directly in the directory entry instead, because FAT has no inodes.

You can read a directory's entries from a program with opendir() and readdir():

#define _DEFAULT_SOURCE
#include <stdio.h>
#include <dirent.h>

int main(int argc, char *argv[]) {
    const char *path = argc > 1 ? argv[1] : ".";
    DIR *d = opendir(path);
    if (!d) { perror("opendir"); return 1; }
    struct dirent *e;
    while ((e = readdir(d)) != NULL)
        printf("inode %-8lu  %s\n", (unsigned long)e->d_ino, e->d_name);
    closedir(d);
    return 0;
}

Running it on a directory proj containing readme.txt and three subdirectories (Linux, ext4):

inode 50777     readme.txt
inode 50757     ..
inode 50776     .
inode 50796     docs
inode 50784     src
inode 50810     tests

Two things to notice:

  • Every directory has the special entries . (itself) and .. (its parent).

  • The order looks random. It is not alphabetical and not the creation order. With the dir_index feature (on by default), ext4 returns directory entries from readdir() in the order of a hash of their names, even for a small directory. POSIX does not promise any order, which is why ls sorts the names itself. Your inode numbers and order will differ.

Directory Operations

Operation

Meaning

POSIX / shell

Search

Find the entry for a given name

done inside open(), stat()

Create a file

Add a new entry

open(O_CREAT)

Delete a file

Remove an entry

unlink(), rm

List

Read all entries

readdir(), ls

Rename

Change an entry's name, or move it to another directory

rename(), mv

Make / remove a directory

Create or delete a directory (must be empty to remove)

mkdir(), rmdir()

Traverse

Visit every directory and file in a subtree

find, backups

Note that a mv within the same file system does not copy any file data: it just removes one directory entry and adds another pointing at the same inode. That is why moving a 10 GB file to another folder is instant, while moving it to a USB drive takes minutes.


Directory Structures

How should directories be arranged? The textbooks describe five designs, each fixing a problem of the previous one.

1. Single-Level Directory

One directory for everyone and everything.

               Root directory
 +------+------+------+-------+------+------+
 | cat  | bo   | a    | test  | data | mail |
 +------+------+------+-------+------+------+
    ↓      ↓      ↓      ↓       ↓      ↓
  file   file   file   file    file   file
  • Simple to implement and understand.

  • Naming problem: every file needs a unique name. If two users both want a file called test, one loses.

  • Grouping problem: no way to keep a project's files together. With thousands of files, remembering names becomes impossible.

Early systems and some very simple devices (old cameras, early floppy-based systems) worked like this.

2. Two-Level Directory

Give each user their own directory. A Master File Directory (MFD) lists the users; each User File Directory (UFD) lists that user's files.

                  MFD
         +--------+--------+--------+
         | user1  | user2  | user3  |
         +--------+--------+--------+
            ↓         ↓         ↓
          UFD       UFD       UFD
       +-----+------+  +------+  +------+-----+
       | cat | test |  | test |  | data | a   |
       +-----+------+  +------+  +------+-----+
  • Fixes naming conflicts between users: user1 and user2 can both have test. A file is identified by a path name such as user1/test.

  • Isolates users, which is good for protection.

  • But no grouping within a user: one user's notes, code and photos are all in one flat list.

  • Sharing is awkward: isolation makes cooperation hard.

  • System programs would have to be copied into every UFD, or kept in a special "system user" directory that is searched automatically. This idea of a list of places to look became the search path (the PATH variable you know today).

3. Tree-Structured Directory

Generalise: let a directory contain both files and other directories (subdirectories), to any depth. This is the structure everyone uses today.

/
├── bin
│   ├── ls
│   └── cat
├── home
│   ├── riya
│   │   ├── notes.txt
│   │   └── projects
│   │       └── os
│   │           └── sched.c
│   └── arjun
│       └── notes.txt
└── etc
    └── hosts
  • Each user can organise their files into any number of subdirectories.

  • Every file has exactly one path from the root, so names are unique as full paths: /home/riya/notes.txt and /home/arjun/notes.txt are different files.

  • Searching is efficient because the search is limited to one directory at each step.

Absolute and Relative Paths

Each process has a current working directory (cwd), stored by the kernel for that process.

  • Absolute path: starts at the root. /home/riya/projects/os/sched.c

  • Relative path: starts at the cwd. If cwd is /home/riya, then projects/os/sched.c names the same file, and ../arjun/notes.txt means /home/arjun/notes.txt.

The weakness of a pure tree: a file belongs to exactly one directory, so it is hard to share. If Riya and Arjun work on the same project file, where does it live?

4. Acyclic-Graph Directory

Allow a file or directory to appear in more than one directory, as long as no cycles form. This is done with links.

        home
       /    \
    riya    arjun
      |       |
  projects  shared ─────┐
      |                 │  (link)
     os  ←──────────────┘
      |
   sched.c

Now /home/riya/projects/os and /home/arjun/shared refer to the same directory. A change made by either user is immediately seen by the other, because there is only one copy. This is how UNIX works in practice, using two kinds of links, described in the next section.

Sharing brings new problems:

  • Multiple names (aliasing): one file now has several paths. A backup program or a disk-usage tool must be careful not to count or copy it twice.

  • Deletion: if Riya deletes the file, what happens to Arjun's link? If the space is freed, Arjun's link points to nothing (a dangling pointer), or worse, to a new file that reuses the space. Solutions: keep a reference count and free the file only when it reaches zero (hard links), or let the link break harmlessly (symbolic links).

5. General-Graph Directory

If links are allowed with no restrictions, a directory can end up inside itself:

   /home/riya/a
        |
        b
        |
   loop ───→ back to /home/riya/a   (cycle!)

Cycles cause two real problems:

  • Infinite traversal: a search like find or a backup would walk round the loop forever, unless it remembers which directories it has visited.

  • Reference counts stop working: in a cycle, each directory is referenced by another member of the cycle, so the counts never fall to zero even when the whole loop is unreachable from the root. Freeing that space needs garbage collection: traverse from the root, mark everything reachable, then free everything unmarked. On a large disk this is very slow.

This is why real systems avoid general graphs. UNIX allows hard links to files only, not to directories, so cycles cannot form through hard links. Symbolic links can form cycles, but they are not counted as real references, and tools either do not follow them or limit how many they follow (Linux gives up with the error ELOOP, "Too many levels of symbolic links").

Comparison

Structure

Same name for two users?

Grouping

Sharing

Main problem

Single-level

No

No

Everything shared

Name collisions

Two-level

Yes

No

Hard

No subdirectories

Tree

Yes

Yes

Hard (one parent)

No sharing

Acyclic graph

Yes

Yes

Yes, via links

Aliasing, deletion

General graph

Yes

Yes

Yes

Cycles, needs garbage collection


UNIX implements the acyclic graph with two kinds of links.

A hard link is an additional directory entry that points to the same inode. A symbolic (soft) link is a separate small file whose content is a path name to another file.

Seeing the Difference

This program creates a file, a hard link and a symbolic link to it, then deletes the original name:

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/stat.h>

static void show(const char *path) {
    struct stat st;
    if (lstat(path, &st) == -1) { printf("%-10s -> (does not exist)\n", path); return; }
    printf("%-10s inode=%lu links=%lu type=%s\n", path,
           (unsigned long)st.st_ino, (unsigned long)st.st_nlink,
           S_ISLNK(st.st_mode) ? "symlink" : "regular");
}

static void cat(const char *path) {
    char buf[64] = {0};
    int fd = open(path, O_RDONLY);
    if (fd == -1) { printf("open(%s) failed\n", path); return; }
    ssize_t n = read(fd, buf, sizeof buf - 1);
    if (n > 0) printf("contents of %s: %s", path, buf);
    close(fd);
}

int main(void) {
    int fd = open("a.txt", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    if (fd == -1) { perror("open"); return 1; }
    if (write(fd, "hello\n", 6) != 6) { perror("write"); return 1; }
    close(fd);

    link("a.txt", "hard.txt");      /* second name for the same inode */
    symlink("a.txt", "soft.txt");   /* new inode that stores the path "a.txt" */

    puts("--- after link() and symlink() ---");
    show("a.txt"); show("hard.txt"); show("soft.txt");

    unlink("a.txt");                /* remove the original NAME */
    puts("--- after unlink(\"a.txt\") ---");
    show("a.txt"); show("hard.txt"); show("soft.txt");
    cat("hard.txt");
    cat("soft.txt");

    unlink("hard.txt"); unlink("soft.txt");
    return 0;
}

Output on Linux (ext4), compiled with gcc -std=c17 -Wall -Wextra:

--- after link() and symlink() ---
a.txt      inode=50811 links=2 type=regular
hard.txt   inode=50811 links=2 type=regular
soft.txt   inode=50812 links=1 type=symlink
--- after unlink("a.txt") ---
a.txt      -> (does not exist)
hard.txt   inode=50811 links=1 type=regular
soft.txt   inode=50812 links=1 type=symlink
contents of hard.txt: hello
open(soft.txt) failed

Read it slowly, because this output explains everything:

  • a.txt and hard.txt have the same inode number. They are two names for one file, equally "real". Neither is the original. The inode's link count is 2.

  • soft.txt has its own inode. It is a tiny file that just contains the text a.txt.

  • After unlink("a.txt"), the link count drops to 1, and the data is still reachable through hard.txt. The file system frees an inode and its blocks only when the link count reaches 0 and no process has the file open.

  • The symbolic link still exists, but the name it points to is gone, so opening it fails. It is now a dangling link.

This is why the system call to delete a file is called unlink: it removes one name. The file disappears only when its last name is gone.

The same experiment from the shell:

echo hello > a.txt
ln a.txt hard.txt        # hard link
ln -s a.txt soft.txt     # symbolic link
ls -li a.txt hard.txt soft.txt
50811 -rw-r--r-- 2 imran imran 6 Nov  2 10:55 a.txt
50811 -rw-r--r-- 2 imran imran 6 Nov  2 10:55 hard.txt
50812 lrwxrwxrwx 1 imran imran 5 Nov  2 10:55 soft.txt -> a.txt

The first column is the inode number and the third is the link count. The symlink's size is 5 bytes: exactly the length of the string a.txt.

Hard link

Symbolic link

What it is

Another directory entry for the same inode

A separate file containing a path

Own inode?

No, shares the target's inode

Yes

Target deleted

Data stays until the last link is removed

Link becomes dangling

Across file systems

No (inode numbers are per file system)

Yes

To directories

Not allowed for users (would allow cycles)

Allowed

Cost to follow

None, it is a normal entry

Extra path lookup

Windows equivalent

NTFS hard link (mklink /H)

Symbolic link (mklink), shortcuts are a different, shell-level idea

Trying to hard-link a directory on Linux is refused:

$ ln proj projlink
ln: proj: hard link not allowed for directory

Directories have hard links too, created automatically: the entry in the parent, the directory's own ., and the .. inside each of its subdirectories. So on traditional UNIX file systems:

link count of a directory = 2 + number of immediate subdirectories

Our proj directory has three subdirectories (src, docs, tests) and one file:

$ stat -c '%n links=%h' proj proj/src proj/readme.txt
proj links=5
proj/src links=2
proj/readme.txt links=1

5 = 2 + 3, and an empty directory like src has 2. (Some file systems, such as Btrfs, do not follow this rule, so do not rely on it in scripts.)


Path Name Resolution

How does open("/home/riya/notes.txt", O_RDONLY) find the file? The kernel walks the path one component at a time:

1. Start at the root directory's inode.      (on ext4 the root is always inode 2)
2. Read root's data, find "home"   → inode 16386
3. Read inode 16386, check it is a directory and that we may search it (x permission)
4. Read its data, find "riya"      → inode of riya
5. Read that inode, read its data, find "notes.txt" → inode of notes.txt
6. Read notes.txt's inode, check read permission → return a file descriptor

(Our root and /home inode numbers come from ls -di / /home on the test machine.) A relative path does the same walk but starts at the process's current working directory instead of the root. At each .. the walk moves to the parent.

Numerical: Disk Reads for a Path Lookup

Count the disk reads needed to open /home/riya/notes.txt and read its first data block, assuming nothing is cached, every directory fits in one block, and each inode needs its own read:

root inode                1
root directory block      1   → finds "home"
home inode                1
home directory block      1   → finds "riya"
riya inode                1
riya directory block      1   → finds "notes.txt"
notes.txt inode           1
notes.txt data block 0    1
                         ---
Total                     8 reads

A path with k components costs about 2k reads for the lookup alone. That is exactly why open() exists (do this once, then use the descriptor), and why the kernel keeps a directory entry cache (Linux calls it the dcache) of recently looked-up names. In practice, / and /home are almost always cached, so real lookups touch the disk rarely.


Implementing a Directory: List or Hash?

Inside one directory, how are the entries stored so that a name can be found quickly?

Linear List

Entries are stored one after another. To find a name, scan from the start.

  • Very simple. Creating a file: scan to make sure the name is not already used, then append.

  • Deleting: mark the entry unused, or move the last entry into its place.

  • Slow for big directories: lookup is O(n). A directory with 100,000 files (a mail spool, a cache folder) needs up to 100,000 comparisons per lookup.

  • Keeping the list sorted allows binary search but makes insertion and deletion more expensive.

Hash Table

Hash the name to find its entry directly.

  • Lookup is O(1) on average.

  • Needs a way to handle collisions (chaining), and a fixed-size table must be rebuilt when it fills up.

  • Listing comes out in hash order, not name order.

Real file systems use a tree or hash-tree that grows gracefully:

  • ext4: a small directory is stored as a simple list of entries inside one block; once it grows beyond one block it becomes an HTree, a hashed B-tree-like index (the dir_index feature). With dir_index on, readdir() walks entries in hash order even for one-block directories, which is why our output above came out scrambled.

  • NTFS, XFS, Btrfs, APFS: B-tree or B+ tree indexes on file names.

  • FAT: a plain linear list, which is one reason FAT gets slow with thousands of files in one folder.

Linear list

Hash table / hash tree

Lookup

O(n)

O(1) average (O(log n) for a tree)

Simplicity

Very simple

More complex

Listing order

Storage order (often insertion order)

Hash order

Used by

FAT, ext2 (no index)

ext4 HTree, NTFS/XFS/Btrfs B-trees


Common Mistakes

  • "A directory is a box that contains files." It contains names that refer to inodes. The file's data is elsewhere, and the same file can be named in two directories.

  • "Deleting a file erases it." rm removes one name. The data is freed only when the link count is 0 and no process has it open. (A process that has a deleted file open can keep using it, which is why disk space sometimes is not freed until a program is restarted.)

  • "A hard link is a shortcut to the original." There is no original. All hard links are equal names for one inode.

  • Thinking a symlink stores an inode number. It stores a path string, which is why it can cross file systems and why it can dangle.

  • Forgetting why hard links to directories are banned. They would allow cycles, which break traversal and reference counting.

  • Expecting readdir() to return sorted names. No order is guaranteed.


Interview Questions

What does a directory entry contain in UNIX?

A file name and an inode number (ext4 also stores the entry length and a file-type hint). All other attributes are in the inode.

What are the disadvantages of a single-level directory?

All files must have unique names, and there is no way to group files by user or project.

What problem does a two-level directory solve, and which remains?

It lets different users use the same file names and isolates users. It still has no subdirectories within a user and makes sharing difficult.

Absolute vs relative path?

An absolute path starts at the root (/). A relative path starts at the process's current working directory.

What problems does an acyclic-graph directory introduce?

A file can have several names, so traversals may visit it twice, and deleting one name raises the question of dangling references, solved by reference counts or by allowing links to dangle.

Why are cycles in a directory graph a problem?

Traversals can loop forever, and reference counts may never reach zero for an unreachable cycle, so garbage collection is needed to reclaim space.

Hard link vs soft link?

A hard link is another name for the same inode and keeps the data alive; it cannot cross file systems or point to directories. A soft link is a separate file holding a path; it can cross file systems and point to directories but can dangle.

Why is the system call for deletion called unlink?

Because it removes one directory entry (link). The inode and data are freed only when no links and no open descriptors remain.

How do file systems make lookups fast in huge directories?

By indexing names with hash tables or trees (ext4 HTree, NTFS and XFS B-trees) and caching recent lookups in memory (the dentry cache).


The Main Idea

Directory       → a file mapping names to inode numbers
Single-level    → one list; name clashes
Two-level       → one list per user; no grouping
Tree            → subdirectories, paths, cwd; no sharing
Acyclic graph   → sharing via links; aliasing and deletion issues
General graph   → cycles; needs garbage collection, so avoided
Hard link       → another name for the same inode (link count)
Symbolic link   → a file containing a path; can dangle
Lookup          → walk the path one component at a time; cached in dcache

Names live in directories, everything else lives in the inode, and a link is just one more name.

We have now followed a file from its name to its inode to its blocks. The last step is the hardware that stores those blocks. In the next chapter, Disk Structure & Disk Scheduling, we look inside a hard disk and see how the OS orders disk requests to keep the slowest part of the system moving.