File systems: inodes, directories, journaling and SSDs

The file system turns a disk, which is just a long row of numbered blocks, into a hierarchy of folders and files with names, permissions and dates. It must do so efficiently for both tiny and huge files, and stay consistent even if power fails in the middle of an operation. In this lesson we look at block allocation methods, the Unix inode with the calculation of the maximum file size, directories and links, permissions, journaling with the reasoning that guarantees its consistency, and the peculiarities of solid-state drives.

Block allocation

The disk is divided into blocks, typically 4 KiB. A file occupies a number of blocks, and the file system must remember which:

• contiguous allocation: the blocks are consecutive; it is enough to remember the first and the count. Very fast reading and easy direct access, but the disk becomes fragmented and a file cannot grow if the next block is taken;
• linked allocation: each block contains the number of the next. No fragmentation, but to reach block 1000 the 999 before it must be read. The FAT of old Windows systems and memory cards keeps the chain in a separate table, read into memory;
• indexed allocation: an index block contains the list of the file’s blocks. Direct access and no external fragmentation; it remains to decide how to handle files with many blocks.

The inode

In Unix every file is described by an inode, which contains everything except the name: size, owner, permissions, dates and the pointers to the blocks. To handle both small and huge files, the pointers are of four kinds.

• 12 direct pointers to data blocks;
• one single indirect pointer to a block containing pointers to data blocks;
• one double indirect to a block of pointers to single indirect blocks;
• one triple indirect, with one more level.

Theorem. With blocks of bytes and pointers of bytes, i.e. pointers per block, the maximum file size is

Proof. The direct pointers address 12 blocks. The single indirect block contains pointers to data: blocks. The double indirect contains pointers, each to a block of pointers to data: blocks. The triple, with one more level, . Adding up and multiplying by the block size gives the formula. ∎

Example. With KiB and 4-byte pointers, : blocks, for a maximum of about 4 TiB. A small file, up to 48 KiB, uses only the direct pointers and is read without additional index blocks: the structure is optimised for the common case, because most files are small. Modern file systems such as ext4 replace the pointers with extents, pairs (first block, length) describing whole contiguous runs with a single entry.

Directories, names and links

A directory is a special file containing pairs (name, inode number). Opening /home/anna/thesis.txt means reading the root directory, finding home in it, reading its inode and directory, and so on. Since the name is in the directory and not in the inode, the same file can have several names: a hard link is another entry pointing to the same inode, which keeps a link count and is freed when it reaches zero. A symbolic link is instead a small file containing a path.

Unix permissions assign read, write and execute (r, w, x) to three categories: owner, group, others. The kernel checks them at every file open, in kernel mode, and a user process cannot bypass them (lesson on virtualisation and security).

Consistency after a failure

Creating a file requires modifying several structures: the free-block map, the inode, the directory. If power fails half way, the disk is left in an inconsistent state: a block marked as used but belonging to no file, or worse, a directory pointing to an uninitialised inode. In the past, at every reboot, a checking program (fsck) examined the whole disk, taking hours on large disks.

Journaling solves this with the write-ahead log technique, the same as databases:

1. the changes of an operation are first written to a sequential area, the journal, followed by a commit record;
2. only then are they applied to the final structures (checkpoint);
3. once the operation is complete, the journal entry can be erased.

After a failure: if the journal contains a committed operation, it is reapplied from the start; if the commit is missing, it is ignored. Reapplying is safe because writing the logged blocks is idempotent: writing the same content twice to the same block gives the same result. Each operation is therefore either fully applied or not at all: this is the atomicity of transactions (Information Systems lesson on transactions). Recovery only requires reading the journal, a few seconds. To save writes, the journal usually contains only metadata, not file data.

Solid-state drives

Flash memories (Digital Systems Electronics lesson on semiconductor memories) have different rules from disks: they are written by pages, but erased only by large blocks, and each block endures a limited number of erasures. A translation layer in the controller (FTL) always writes to new pages, keeps the mapping between logical and physical addresses, spreads wear over all blocks (wear leveling) and reclaims the space of obsolete pages in the background. The TRIM command lets the operating system tell the SSD which blocks are no longer needed, so reclamation need not copy them uselessly. There is no longer any head seek time: the algorithms that ordered disk requests to reduce arm movements lose importance, and what counts instead is keeping many requests in flight in parallel.