Module 8: File systems

File systems: inodes and links

A file is not its name. Follow each operation through the directory, the inode table and the blocks, and find out when data is really deleted.

30 min

Before you start

  • What a process is (lesson Processes and their states).
  • The idea of a block: a fixed-size piece of the disk, like pages and frames in memory (the lesson Virtual memory and paging helps but is not required).

Theory

A file system divides the disk into blocks: 4 bytes here, 4 KiB in real systems.

Every file has an inode, identified by its number. The inode stores the type (file, directory or symbolic link), the size, the link count and the pointers to its data blocks. The inode does not store the name.

A directory is a special file whose content is a list of entries name → inode number. Here there is a single directory, the root /: inode 0, stored in block 0.

Two bitmaps say which inodes and which blocks are in use (1) or free (0). New inodes and blocks take the lowest free number.

Operation Like What it does
create name open with O_CREAT | O_EXCL New inode, empty file, new entry. Fails if the name exists.
write name text writing the whole file Frees the old blocks and takes ⌈length ÷ 4⌉ new ones.
link old new ln old new Hard link: another entry for the same inode; its count goes up.
symlink target new ln -s target new Symbolic link: a new inode whose content is the name target.
unlink name rm name Removes the entry; the count goes down.
open name / close fd Gives and returns a file descriptor (3, 4…).
cat name / read fd Reads through a name or through a descriptor.
rename old new mv old new Changes the entry’s name.

Example: create a and then write a "hey": inode 1, size 3, and block 1 holds hey.

Predict

The board starts with the Links script:

  1. create notas.txt
  2. write notas.txt "hola mundo"
  3. link notas.txt copia.txt
  4. symlink notas.txt atajo
  5. unlink notas.txt
  6. cat copia.txt
  7. cat atajo

What does step 6 show? And step 7? For each one: “hola mundo”, an empty file or an error. Answer in the Your prediction panel before you run.

Run

Operation script

One operation per step. Names in lowercase letters, digits, dot, dash or underscore; texts up to 12 characters.

  1. Step 1
  2. Step 2
  3. Step 3
  4. Step 4
  5. Step 5
  6. Step 6
  7. Step 7
Scenarios

Your prediction

What does each read in the script show?

The board before the first turn

One directory, 8 inodes and 12 blocks of 4 bytes.

Inodes
Blocks

Directory /

  • No entries

Open descriptors

  • None

Inode table

Data blocks

  1. 0 directory
  2. 1 free
  3. 2 free
  4. 3 free
  5. 4 free
  6. 5 free
  7. 6 free
  8. 7 free
  9. 8 free
  10. 9 free
  11. 10 free
  12. 11 free

What happened this turn

Press Run or step through. Here you will see which layer each operation touches: names, inodes or blocks.

Output

No reads yet.

As it runs, watch four moments:

  • Step 2: how many blocks does “hola mundo” take? Who points to them?
  • Step 3: is any new block or inode allocated?
  • Step 5: the entry notas.txt disappears. Do inode 1 and its blocks disappear too?
  • Step 7: which name does the system look up when it follows atajo?

The tokens tie the three layers together: the same shape and color mark a directory entry, its inode and its blocks.

Explain

This stage opens when you run the simulation to the end.

Go to the simulation

The right answers were: step 6 shows “hola mundo” and step 7 gives an error.

The name is not the file. The directory only maps names to numbers; everything else is in the inode. After step 3, notas.txt and copia.txt are two names for inode 1, and neither one is “the original”. Removing notas.txt lowers inode 1’s link count from 2 to 1 and nothing else changes. ls -i shows inode numbers and stat shows the link count.

A hard link is not a copy. No block was allocated: the data exists only once. A hard link cannot cross file systems (inode numbers belong to each file system), and most systems forbid hard links to directories so the tree has no cycles.

A symbolic link stores a name. atajo is a separate inode whose content is the text notas.txt. To read it, the system looks that name up in the directory, and at step 7 it is gone: a dangling link. Symbolic links can cross file systems and point to directories, but they keep nothing alive. ext4 stores short targets (under 60 bytes) inside the inode itself, with no blocks, just like this simulator.

When data is freed. Only when the link count reaches 0 and no process has the file open. A process can keep reading a file after its last name is removed; the space comes back when it closes it (the Open file script). lsof +L1 lists such open, deleted files; on Linux they also show as (deleted) under /proc/<pid>/fd.

Renaming does not move data. mv within the same file system rewrites a directory entry; the inode number and every block stay where they were. That is why moving a 10 GB file is instant.

Inodes run out too. df -i shows how many are left. Many tiny files can exhaust the inodes while blocks are still free.

Real systems. ext4 uses 256-byte inodes and 4 KiB blocks, and describes data with extents (a starting block and a length) instead of one pointer per block. The ext2/ext3 inode (like BSD FFS) has 12 direct pointers plus single, double and triple indirect blocks.

Experiment

This stage opens when you run the simulation to the end.

Go to the simulation

Use the board to solve these challenges. Each one has a possible solution when you expand it.

1. Read a file’s data after all its names have been removed.

Load Open file. At step 4 log.txt is removed, but step 5, read 3, shows “datos”: the descriptor points to the inode, which lives on while it is open. Closing it at step 6 frees the inode and its blocks, and step 7 reuses inode 1.

2. Free the blocks of a file that has two names.

In Links, change step 6 to unlink copia.txt. The count reaches 0, nobody has it open, and inode 1 and blocks 1, 2 and 3 are freed.

3. Make atajo work again without touching it.

In Links, after step 5: create notas.txt, write notas.txt "otra" and cat atajo. The symbolic link looks the name up again and finds the new inode 3: it reads “otra”.

4. Show that renaming does not touch the data.

In Links, change step 6 to rename copia.txt final.txt. The entry gets a new name, but it still points to inode 1, with the same blocks 1, 2 and 3.

Check

This stage opens when you run the simulation to the end.

Go to the simulation
1. ln a b (a hard link). How many inodes and how many copies of the data are there now?
2. A file has link count 2. You rm one of its names. Are its blocks freed?
3. A process has a file open and you remove its only name. When does the space come back?
4. ln -s a b and then rm a. What does cat b do?
5. mv big.iso copy.iso on the same file system. What changes?
6. Where is a file's name stored?

Go deeper

  • Subdirectories, . and .., and why a directory’s link count is 2 plus its number of subdirectories.
  • Journaling and crash consistency. What happens if the power fails between updating the bitmap and the inode.
  • ext4 extents and indirect blocks: how large a file one inode can describe.
  • Copy-on-write file systems (Btrfs, ZFS) and reflinks: copies that share blocks until someone writes.

Further reading:

  • Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces, ch. 39 (sections 39.14 and 39.15) and ch. 40. Free online.
  • Silberschatz, Galvin and Gagne, Operating System Concepts, 10th ed., ch. 13 and 14.
  • unlink(2) and symlink(7) manual pages: man7.org.
  • Linux kernel documentation, ext4 Data Structures and Algorithms: docs.kernel.org.