Core · Operating systemsLesson 6 of 6Free to read

File systems · Operating Systems

How does a file system turn a path into bytes on a disk?

Why you need it

A disk only stores numbered blocks. The file system adds names, folders, sizes and permissions on top. Knowing how (inodes, blocks, directory entries) explains why a disk can be "full" with space left, how hard links work, why deleting an open log doesn't free space, and how ls -l gets its numbers.

The intuition

A block is a fixed-size chunk of the disk (often 4 KB).
An inode describes one file: its size, owner, permissions and the list of blocks holding its data. It has a number, not a name.
A directory is a special file that maps names to inode numbers.

So opening /home/ada/notes.txt means: look up home in the root directory → inode → that directory's entries → ada → … → notes.txt → inode → blocks.

Two names pointing at the same inode are hard links. The data is freed only when no name and no open program refers to the inode any more.

Definition

Inode

A record describing one file (size, owner, mode, timestamps, block list). Directories map names to inode numbers.

Block

The unit the disk is divided into. A file uses whole blocks, so a 1-byte file still takes one block.

Examples

Resolve a path

Try it yourself

A tiny file system: directories map names to inode numbers; inodes hold the data.

inodes = {
    1: {"type": "dir", "entries": {"home": 2, "etc": 5}},
    2: {"type": "dir", "entries": {"ada": 3}},
    3: {"type": "dir", "entries": {"notes.txt": 4}},
    4: {"type": "file", "data": "buy milk"},
    5: {"type": "dir", "entries": {}},
}

def lookup(path):
    ino = 1
    for name in path.strip("/").split("/"):
        node = inodes[ino]
        if node["type"] != "dir" or name not in node["entries"]:
            return None
        ino = node["entries"][name]
    return ino

print(lookup("/home/ada/notes.txt"))
print(inodes[lookup("/home/ada/notes.txt")]["data"])
print(lookup("/etc/passwd"))

Step by step

L10Start at the root directory, inode 1.
L15Each name leads to the next inode.
L18home → 2, ada → 3, notes.txt → 4.4
L20No such entry in /etc.None

Common mistakes

Deleting a log that's still open

rm removes the name, but the program writing it still holds the inode, so the space isn't freed until it closes the file or restarts.

Out of inodes

Millions of tiny files can use up all inodes while blocks are still free: "No space left on device" with free space showing. Check with df -i.

Quick quiz

1. What does this print?

import math
BLOCK = 4096
for size in [1, 4096, 4097, 10000]:
    print(size, math.ceil(size / BLOCK))

A
```
1 1
4096 1
4097 2
10000 3
```
B
```
1 0
4096 1
4097 1
10000 2
```
C
```
1 1
4096 2
4097 2
10000 3
```

Show the answer

Answer: A

A file always uses whole blocks: round up.

2. `notes.txt` and `copy.txt` are hard links to the same inode. You `rm notes.txt`. What happens to the data?

AIt stays; copy.txt still points at it
BIt's deleted
Ccopy.txt becomes empty

Show the answer

Answer: A

The inode keeps a link count. Data is freed only when it reaches zero.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictLink counts
Type exactly what this program prints.
ModifyCount whole blocks
disk_usage(sizes, block) should return how many bytes of disk a list of files really uses. It sums the file sizes, but every file takes whole blocks. Fix it.
WriteList a directory
Using the same structure as the example, write ls(inodes, path) that returns the sorted names inside the directory at path ("/" means the root, inode 1). Return None if the path doesn't exist or isn't a directory.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
File system	文件系统	The layer that turns disk blocks into named files and folders.
Inode	索引节点	The record describing one file: size, owner, mode and blocks.
Hard link	硬链接	Another name for the same inode.