22.1. File System Layout

To store a file system on a real disk, the high-level objects (directories, files, symbolic links) must be translated into read and write operations on disk blocks identified by logical block addresses. How do we do that? How do we even know what file system should be used to understand the blocks on the disk? How do we load the operating system in the first place off of the disk?

Fig. 22.1 Base disk layout with partition table

As shown in Fig. 22.1 the operating system normally writes a partition table at the beginning of the disk that can be used to divide the disk into partitions, each potentially containing a different file system. For each partition, the table indicates the range of blocks in it, whether the partition contains an operating system that could be executed, and the type of file system that should be used to interpret the blocks.

When a system starts up, the firmware will read the partition table, look at which partitions contain operating systems, and decide which one to boot (potentially asking the user). It then reads the boot block of that partition, and starts executing code from that block that will in turn read other blocks…

Fig. 22.2 Example of a file system that might be in a partition.

Fig. 22.2 shows example contents of a partition. After the boot block, all the information is specific to the particular file system on that partition. Once the operating system kernel is started, it will use the file system type information from the partition table to figure out if it understands that kind of file system. Recall, there are hundreds and hundreds of file systems, and operating systems like Linux have file system code specific to each one. When we talked about operating system structure we talked about how the file system code is normally dynamically loaded (see Fig. 3.3); if the operating system had all the file systems it could possibly understand loaded, it would be huge.

While every file system does it differently, Fig. 22.2 shows on example organization for a simple file system. Key elements on disk are:

• Superblock: describes the overall file system, including where the inodes are, where free block information is kept, the block size, the inode number for the root directory, … and all kinds of information for how to recover the file system if failures occur.

• Free info: some data structure to describe which blocks in the partition or disk are free.

• Inodes: an array of inode information indexed by inode number.

The remainder of the partition is just disk blocks, which are used by the file system to store files and directories.

Note that instead of 512-byte sectors, file systems traditionally use disk blocks, which are some small power-of-two multiple of the sector size, typically 1KB, 2KB, or 4KB. Reading and writing is performed in units of complete blocks, and file system addresses are stored as disk block numbers rather than LBAs. These disk block numbers must be multiplied by the appropriate value before being passed to the disk. Since modern disk drives have an internal sector size of 4 KB (despite pretending to support 512-byte sectors) and the virtual memory page size is 4 KB on most systems today, that has become a very common file system block size.

the next four chapters describe key file system design decisions, namely how to:

1. keep track of the blocks used in a file

2. keep track of the free blocks

3. maintain the name space

4. deal with failures