File Systems & Storage — From a Name to Disk Blocks
What you'll learn
- How a file system lays out a disk: superblock, bitmaps, the inode table and data blocks
- What an inode stores (and the one thing it does not: the file's name), and how directories map names to inode numbers
- How an inode finds its blocks with direct and indirect pointers or extents, and what limits a file's size
- The difference between hard links and symbolic links, and when a file's space is really freed
- How the page cache speeds things up, why a crash can corrupt a naive file system and how journaling prevents it
- The trade-offs between ext4, XFS, Btrfs and friends
You will code an inode block mapper in Go, a links-and-inodes simulator in Python and a journal recovery tool in Java.
A disk is a long row of numbered blocks 🧱
A drive offers the OS one thing: an array of fixed-size blocks (commonly 4 KiB in a file system) that can be read or written by number. Files, folders and names are an illusion that a file system builds on top: a data structure stored in those blocks. A very small one, in the style of the simple file system in OSTEP, looks like this:
block: 0 1 2 3 ... 7 8 ... 63
+--------+----------+----------+-------------+-----------------+
| super | inode | data | inode table | data blocks |
| block | bitmap | bitmap | (inodes) | (file contents) |
+--------+----------+----------+-------------+-----------------+
- The superblock describes the file system: its type, size, block size and where everything else starts
- Two bitmaps record which inodes and which data blocks are free (one bit each)
- The inode table holds fixed-size records, one per file, numbered from 1 upwards
- Data blocks hold file contents and directory listings
ext4 uses the same ideas, repeated in block groups spread across the disk.
The inode: everything except the name
An inode (index node) describes one file. inode(7) lists what it stores: the file type and mode (permission bits), the owner UID and GID, the size, timestamps (last access, last modification, last status change and, on some file systems, creation), the link count, and where the data blocks are. Run stat notes.txt to see them.
What is not in the inode is the name. Names live in directories. A directory is just a file whose content is a list of directory entries: pairs of name → inode number. Every directory also lists . (itself) and .. (its parent). ls -i prints the inode numbers.
Following a path
Opening /home/ana/notes.txt means walking the tree. On ext2/3/4 the root directory is always inode 2, so the kernel:
- reads inode 2, then its data block, and finds
home → 4321 - reads inode 4321, then its data block, and finds
ana → 5120 - reads inode 5120, then its data block, and finds
notes.txt → 6007 - reads inode 6007, which says where the bytes are
That is seven reads before the first byte of data. Real kernels keep recently used inodes and names in memory (the inode cache and the dentry cache), so a second lookup costs almost nothing.
The name notes.txt appears only in block 377, the content of directory ana. The file's inode knows its size and blocks but not its name. Add a deeper directory to see how every level costs two more reads.
# A toy disk: inodes, and the data blocks of directories (name -> inode number).
inodes = {
2: {"type": "dir", "block": 100}, # inode 2 is the root directory on ext2/3/4
4321: {"type": "dir", "block": 230},
5120: {"type": "dir", "block": 377},
6007: {"type": "file", "size": 1800, "block": 912},
}
blocks = {
100: {".": 2, "..": 2, "home": 4321, "etc": 12},
230: {".": 4321, "..": 2, "ana": 5120},
377: {".": 5120, "..": 4321, "notes.txt": 6007},
}
def lookup(path):
reads = 0
number = 2 # start at the root inode
for name in [p for p in path.split("/") if p]:
node = inodes[number]; reads += 1 # read the directory's inode
entries = blocks[node["block"]]; reads += 1 # read its data block
number = entries[name]
print(f" '{name}' found in block {node['block']} -> inode {number}")
reads += 1 # finally read the file's own inode
print(f" {path}: inode {number}, {inodes[number]['size']} bytes, {reads} disk reads")
lookup("/home/ana/notes.txt")
Finding the data blocks: pointers and extents
An inode has room for only a handful of block addresses. The classic Unix design (used by ext2 and ext3) builds a small tree:
inode
├── direct[0] ... direct[11] ──▶ data blocks 0-11
├── single indirect ──▶ [ 1024 pointers ] ──▶ data blocks
├── double indirect ──▶ [ 1024 ] ──▶ [ 1024 each ] ──▶ data blocks
└── triple indirect ──▶ [ 1024 ] ──▶ [ 1024 ] ──▶ [ 1024 ] ──▶ data blocks
With 4 KiB blocks and 4-byte block numbers, one indirect block holds 4096 / 4 = 1024 pointers, so:
- 12 direct pointers reach 12 × 4 KiB = 48 KiB
- the single indirect block adds 1024 × 4 KiB = 4 MiB
- the double indirect block adds 1024² × 4 KiB = 4 GiB
- the triple indirect block adds 1024³ × 4 KiB = 4 TiB
Small files, which are the vast majority, need no extra reads at all; a byte deep inside a huge file costs up to three extra reads for the indirect blocks. (Other inode fields can lower the real limit: ext3 caps files at 2 TiB with 4 KiB blocks.)
ext4 replaces most of this with extents: one entry says "logical blocks 0-999 are physical blocks 81,920-82,919". A single extent covers up to 32,768 blocks (128 MiB with 4 KiB blocks), so a large file written in one go needs a few entries instead of thousands of pointers.
Lab exercise 1
GoGraded in Code LabMap byte offsets of a file to the pointer that leads to their data block, in a classic inode with direct, single, double and triple indirect pointers.
Input (whitespace-separated numbers):
block_size ptr_size direct: the block size in bytes, the size of one block number in bytes, and the number of direct pointers in the inode- then zero or more byte offsets until the end of input
Rules: k = block_size / ptr_size pointers fit in one indirect block. The logical block of an offset is n = offset / block_size. Blocks 0 to direct-1 are direct; the next k go through the single indirect block, the next k² through the double, the next k³ through the triple. Inside each region number from 0: for the double, entry i = n / k of the top block and j = n % k below it; for the triple, n / k², (n / k) % k and n % k. Fetching the data block costs 1, 2, 3 or 4 disk reads (the inode is already in memory).
Output: first max file size: <bytes> bytes (all reachable blocks times the block size), then for each offset:
<offset> -> block <n> via <path>, reads=<r>with<path>one ofdirect[a],single[a],double[a][b],triple[a][b][c]- or
<offset> -> TOO LARGE
Example: 4096 4 12 and the offsets 0 49152 4243456 print
max file size: 4402345721856 bytes
0 -> block 0 via direct[0], reads=1
49152 -> block 12 via single[0], reads=2
4243456 -> block 1036 via double[0][0], reads=3
- Example from the prompt
- Last byte of each region
- Triple indirect and beyond the limit
- 1 KiB blocks
- 8-byte pointers and only 4 direct blocks
Example run
- Input
4096 4 12 0 49152 4243456
- Expected output
max file size: 4402345721856 bytes 0 -> block 0 via direct[0], reads=1 49152 -> block 12 via single[0], reads=2 4243456 -> block 1036 via double[0][0], reads=3
package main
import "fmt"
// locate maps a logical block number to its place in the pointer tree and the
// number of disk reads needed to fetch that data block (the inode is already in
// memory). ok is false when the block lies beyond the triple indirect tree.
func locate(n, direct, k uint64) (path string, reads int, ok bool) {
// TODO 1: n < direct -> "direct[n]", 1 read
// TODO 2: subtract direct; n < k -> "single[n]", 2 reads
// TODO 3: subtract k; n < k*k -> "double[n/k][n%k]", 3 reads
// TODO 4: subtract k*k; n < k*k*k -> "triple[a][b][c]", 4 readsMore lines in Code Lab: 29
Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.
JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.
Hard links and symbolic links 🔗
Because names and inodes are separate, one inode can have several names:
directory docs/ inodes
report.txt ──┐
├──▶ inode 1201 (file, links = 2) ──▶ data blocks
final.txt ──┘
latest ──▶ inode 1305 (symlink, links = 1) ──▶ "report.txt"
- A hard link (
ln report.txt final.txt) is a second directory entry with the same inode number. Both names are equally real; the inode's link count (the number after the permissions inls -l) is now 2. Hard links cannot cross file systems (inode numbers are unique only inside one) and cannot point to directories - A symbolic link (
ln -s report.txt latest) is a separate, tiny file whose content is a path. The kernel follows it during path resolution. It can point anywhere, even to another file system or to a directory, and it dangles when its target disappears. Linux gives up after following 40 symbolic links in one lookup (errorELOOP)
rm does not really "delete a file": it calls unlink(), which removes one name and decrements the link count. The inode and its blocks are freed only when the link count reaches 0 and no process still has the file open. That is why deleting a huge log that a running service still writes to frees no space until the service closes it (lsof +L1 lists such files).
Lab exercise 2
PythonGraded in Code LabSimulate one directory of a file system with inodes, hard links and symbolic links.
Input: one command per line:
create NAME TEXT: a new regular file whose content is TEXT (the rest of the line)link EXISTING NEW: a hard link. NEW becomes another name for the same inode as EXISTING (like Linuxlink(), it does not follow symlinks)symlink TARGET NAME: a new symbolic link whose content is the name TARGET (which need not exist)rm NAME: remove the name; the inode loses one link and is freed when it has none leftcat NAME: print the file's content, following symlinks
Rules:
- Inode numbers start at 1, go up by one for every new inode (files and symlinks) and are never reused. A new inode has 1 link.
- Errors print one line and change nothing:
create NAME: File exists,symlink NAME: File exists,link NEW: File exists(checked after EXISTING),link EXISTING: No such file or directory,rm NAME: No such file or directory, and forcateithercat NAME: No such file or directory(a missing name anywhere on the way) orcat NAME: Too many levels of symbolic links(more than 40 symlinks followed) - At the end print every name in sorted order as
<inode> <links> <name>, plus-> <target>for a symlink, theninodes in use: <count>
Example:
create report.txt draft v1
link report.txt final.txt
symlink report.txt latest
rm report.txt
cat final.txt
cat latest
prints
draft v1
cat latest: No such file or directory
1 1 final.txt
2 1 latest -> report.txt
inodes in use: 2
- Example: a hard link survives rm, a symlink dangles
- A chain of 40 symlinks works; 41, or a loop, is too many
- Errors change nothing
- Link counts and inode numbers that are never reused
- A hard link to a symlink shares its inode; rm removes the link, not its target
- Empty input
Example run
- Input
create report.txt draft v1 link report.txt final.txt symlink report.txt latest rm report.txt cat final.txt cat latest
- Expected output
draft v1 cat latest: No such file or directory 1 1 final.txt 2 1 latest -> report.txt inodes in use: 2
import sys
MAX_SYMLINKS = 40 # Linux gives up after following 40 symbolic links
inodes = {} # inode number -> {"type": "file" or "symlink", "links": n, "data": text}
names = {} # the directory: name -> inode number
next_inode = 1
def new_inode(kind, data):
global next_inode
number = next_inode
next_inode += 1More lines in Code Lab: 18
Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.
JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.
The page cache, crashes and journaling 📒
Disks are slow compared with RAM, so Linux keeps recently used file data in the page cache. Reads of cached data never touch the disk (free -h shows the cache as buff/cache). Writes normally land in the cache too: the page is marked dirty and written back later, typically within about 30 seconds (vm.dirty_expire_centisecs). A program that must not lose data calls fsync(fd), which returns only after that file's data and metadata have reached the device; databases do this on every commit.
The crash-consistency problem
Appending one block to a file needs three separate writes: the data block, the inode (new pointer and size) and the data bitmap (block now used). The disk completes them one at a time, and the power can fail in between. Depending on which writes made it, the file system is fine, leaks space, or has an inode pointing at a block that is marked free. See every case:
Only two of the eight outcomes are what we want: all three writes or none of them. Journaling exists to make the update all-or-nothing. Notice that 'data only' looks harmless but silently loses the new data.
// Appending one block needs three separate writes. What if power fails between them?
const writes = ["bitmap", "inode", "data"];
function verdict(done) {
const b = done.has("bitmap"), i = done.has("inode"), d = done.has("data");
if (i && !b) return "INCONSISTENT: the inode points to a block the bitmap calls free";
if (b && !i) return "INCONSISTENT: block marked used, but no inode points to it (space leak)";
if (i && b && !d) return "consistent metadata, but the file now contains garbage";
if (i && b && d) return "consistent: the append happened";
return "consistent: as if the append never happened";
}
for (let mask = 0; mask < 8; mask++) {
const done = new Set(writes.filter((_, k) => mask & (1 << k)));
const label = done.size ? [...done].join(" + ") : "nothing";
console.log((label + " reached the disk").padEnd(40) + verdict(done));
}
Journaling: write it down first
The old fix was fsck: after a crash, scan every inode and bitmap and repair contradictions. On a multi-terabyte disk that can take hours. A journaling file system (ext3, ext4, XFS) instead uses write-ahead logging, the same idea databases use:
- Journal write: write the blocks you are about to change into a reserved area, the journal
- Journal commit: once those writes are on disk, write a small commit record. The transaction has now officially happened
- Checkpoint: write the blocks to their real locations
- Free the transaction's space in the journal
After a crash the kernel replays every transaction that has a commit record and ignores the rest. Replay is safe to repeat (writing the same value to a block twice changes nothing), so even a crash during recovery is harmless. Recovery takes seconds because only the journal is read.
Writing everything twice is expensive, so ext4 by default uses ordered mode (data=ordered): only metadata goes through the journal, and data blocks are written to their final place before the metadata that points to them is committed. data=journal logs file data too; data=writeback drops the ordering for speed. Copy-on-write file systems (Btrfs, ZFS) take another route: they never overwrite live blocks, they write new copies and then switch one root pointer atomically.
Lab exercise 3
JavaGraded in Code LabWrite the recovery step of a journaling file system: replay committed transactions and discard the rest.
Input:
- Line 1: the disk as it was before the journal was written: one word per block, block 0 first
- Then the journal records that survived the crash, one per line:
begin T: transaction T startswrite T B VALUE: T will set block B (0-based) to VALUEcommit T: T's commit record reached the disk
- The journal is well formed: every
writeandcommitnames a transaction that has begun, and none commits twice. Transactions may interleave. Blank lines are ignored.
Recovery rule: apply the writes of every committed transaction, transaction by transaction in commit order, each one's writes in journal order. Transactions without a commit record are discarded.
Output: three lines:
replayed: <ids in commit order, or none>
discarded: <ids of uncommitted transactions in begin order, or none>
disk: <every block after recovery>
Example:
a b c d
begin T1
write T1 0 A
write T1 2 C
commit T1
begin T2
write T2 1 B
prints
replayed: T1
discarded: T2
disk: A b C d
- Example from the prompt
- Interleaved transactions: commit order decides
- Crash before any commit
- An empty journal
- The same block twice in one transaction, and blank lines
Example run
- Input
a b c d begin T1 write T1 0 A write T1 2 C commit T1 begin T2 write T2 1 B
- Expected output
replayed: T1 discarded: T2 disk: A b C d
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String first = in.readLine();
if (first == null) return;More lines in Code Lab: 24
Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.
JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.
Choosing a Linux file system
- ext4: the default on Debian and Ubuntu. Mature, journaled, uses extents, can be grown and (offline) shrunk. A safe default for almost anything
- XFS: the default on Red Hat Enterprise Linux since version 7. Excellent with large files and many parallel writers; it can be grown but not shrunk
- Btrfs: copy-on-write with snapshots, checksums on data and metadata, compression and multi-disk support; the default on Fedora Workstation and openSUSE. More features, more to learn
- ZFS (through OpenZFS): similar ideas to Btrfs and popular on storage servers, but kept outside the mainline kernel because its CDDL license is considered incompatible with the GPL
- tmpfs: a file system in RAM (and swap), used for
/runand/dev/shm; everything in it vanishes at reboot - FAT32 / exFAT: for USB sticks and SD cards shared with other systems; no Unix permissions, and FAT32 cannot store a file of 4 GiB or more
df -hT shows each mounted file system with its type, and lsblk -f lists the disks and partitions underneath.
Question 1 of 5
Where is a file's name stored?
Question 2 of 5
With 4 KiB blocks, 4-byte block pointers and 12 direct pointers, which pointer leads to the block that holds byte 50,000 of a file?
Question 3 of 5
You rm a 20 GB log file, but df shows no free space gained. What is the most likely cause?
Question 4 of 5
What does a journaling file system do when it mounts after a crash?
Question 5 of 5
Which statement about symbolic links is true?
Summary
- A file system is a data structure on numbered blocks: superblock, bitmaps, inode table, data blocks
- An inode holds type, mode, owner, size, timestamps, the link count and the block map, but not the name; directories map names to inode numbers, and the root is inode 2 on ext2/3/4
- Blocks are found through direct and indirect pointers (48 KiB, 4 MiB, 4 GiB and 4 TiB reach with 4 KiB blocks) or, on ext4, extents
- A hard link is another name for the same inode; a symbolic link is a small file holding a path. Space is freed at 0 links and no open descriptors
- The page cache absorbs reads and writes;
fsyncforces data to disk. Journaling (write-ahead logging) makes multi-block updates all-or-nothing, and ext4's default isdata=ordered - ext4 is the safe default, XFS shines with big parallel workloads, Btrfs brings snapshots and checksums
- You wrote an inode block mapper, a links-and-inodes simulator and a journal recovery tool
Practice: on a Linux machine try stat, ls -li, ln and ln -s in a scratch directory, watch the link count change, and run df -hT. Next: virtualization and containers, where mount namespaces and layered file systems give every container its own view of the tree.
Practice
Reading is not learning until you run something. Pick one.
Graded lab exercises
- Lab exercise 1GoNot passed yet Try in Code Lab
- Lab exercise 2PythonNot passed yet Try in Code Lab
- Lab exercise 3JavaNot passed yet Try in Code Lab