Introduction to File Systems

open("foo"): "I’d like to use the file named foo."

close("foo"): "I’m finished with foo."

read(2): "I’d like to perform a read from file handle 2 at the current position."

write(2): "I’d like to perform a write from file handle 2 at the current position."

lseek(2, 100): "Please move my saved position for file handle 2 to position 100.

dup2 is really about manipulating a processes names for files and doesn’t have much to do with the file system.

Letter to Mom: LetterToMom.txt

Letter to Suzanna: LetterToSuzanna.txt

Letter to Chuchu: WoofWoofWagWag.txt

Another letter to Suzanna: AnotherLetterToSuzanna.txt

A third letter to Suzanna: LetterToSuzanna22Mar2012.txt

letters/Mom/Letter.txt

letters/Chuchu/WoofWoofWagWag.txt

letters/Suzanna/Letters/1.txt

letters/Suzanna/Letters/2.txt

letters/Suzanna/Letters/2.txt

Location requires navigation and relative navigation is useful, meaning that locations (directories) can include pointers to other locations (other directories).

Finally, location is only meaningful if it is tied to a files name, so hierarchical file systems implement name spaces, which require that a file’s name map to a single unique location within the file system.

Files, including some number of file attributes and permissions.

Names, organized into a hierarchical name space.

Data blocks: contain file data.

Index nodes (inodes): contain not file data.

On-disk layout. How does the file system decide where to put data and metadata blocks in order to optimize file access?

Data structures. What data structures does the file system use to translate names and locate file data?

Crash recovery. How does the file system prepare for and recover from crashes?

File systems are really maintaining a large and complex data structure using disk blocks as storage.

This is hard because making changes potentially requires updating many different structures.

From the perspective of a process all of these things need to happen synchronously.

In reality, many different asynchronous operations are involved touching many different disk blocks. (Each operation above modifies at least one disk block.)

This creates both a consistency and a performance problem!

translate paths to file index nodes or inodes.

find data blocks associated with a given inode (file).

allocate and free inodes and data blocks.

Sector: the smallest unit that the disk allows to be written, usually 256 bytes.

Block: the smallest unit that the file system actually writes, usually 4K bytes.

Extent: a set of contiguous blocks used to hold part of a file. Described by a start and end block.

Because contiguous writes are good for disk head scheduling and 4K is the page size which affects in-memory file caching.

Because contiguous writes are good for disk head scheduling and many files are larger than 4K!

1 inode per file.

256 bytes, so 1 per sector or 16 per block.

Location of file data blocks (contents).

Permissions including user, read/write/execute bits, etc.

Timestamps including creation (crtime), access (atime), content modification (mtime), attribute modification (ctime) and delete (dtime) times.

Named and located by number.

All inodes are created at format time at well-known locations.

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.