File System Data Structures

`ext4` inodes

How does the system translate an inode number into an inode structure?

What are the consequences of this?

inodes may not be located near file contents. ext4 creates multiple blocks of inodes within the drive to reduce seek times between inodes and data.
Fixed number of inodes for the file system. Can run out of inodes before we run out of data blocks! ext4 creates approximately one inode per 16 KB of data blocks, but this can be configured at format time.

Simply a special file the contents of which map inode numbers to relative names.

open("/etc/default/keyboard") must translate "/etc/default/keyboard" to an inode number.

Get inode number for root directory. This is usually a fixed agreed-on inode number, like 2.
Open the directory with inode number 2. Look for "etc". Find "etc" with inode number 393218.
Open the directory with inode number 393218. Look for "default". Find "default" with inode number 393247.
Open the directory with inode number 393247. Look for "keyboard". Find keyboard with inode number 394692.
Open the file with inode number 394692.

read/write(filehandle, 345) must translate 345 to a data block within the open file to determine what data block to modify.
There are multiple ways of doing this.

One solution: organize data blocks into a linked list.

Pros:

Cons:

A second solution: store all data blocks in the inode in a single array allocated at file creation time.

Pros:

Cons:

Observation: most files are small, but some can get very large.

Have inode store:

some pointers to blocks, which we refer to as direct blocks.
some pointers to blocks containing pointers to blocks, which we refer to as indirect blocks.
some pointers to blocks containing pointers to blocks containing pointers to blocks, which we refer to as doubly indirect blocks.
etc…