File systems

Gaël Thomas

Device and device driver

Device and device driver

Devices in UNIX

2 types of peripherals

Block devices in xv6

Principle of the virtio_disk_rw algorithm

xv6 is written to run on a virtual machine, i.e., on a special environment where devices are indeed virtualized. One interface designed to perform best with those virtual devices is the virtio interface. While the virtio protocol is different from the one used by real, physical block devices (e.g., IDE or SATA), in both cases, DMA and interruptions are used.

The I / O cache

Principle of an I/O cache

The xv6 buffer cache

How the buffer cache works: buffer management (1/3)

How the buffer cache works: read buffer (2/3)

How the buffer cache works: write buffer (3/3)

The log

Operation versus writing to disk

Consistency issues

Bad solutions

First idea: transactions

Second idea: log

Third idea: parallel log

Log structure

\(\rightarrow\) The system can therefore manage up to 3 copies of a block

Log algorithm principle

Using the log

b = bread(...);
// Modify data of b

Implementation in xv6 (1/3)

Implementation in xv6 (2/3)

The log controls block writes and releases through log_write() and end_op(). System calls that implement access to blocks never use bwrite() and brelse() directly. Instead, the log keeps track of blocks that must be written to disk: they are called dirty blocks, because their content cached in the buffer cache is different from their content in the filesystem on the disk.

Implementation in xv6 (3/3)

Partitions and file systems

File system

Principle of a file system


Disk image

UFS/xv6 file system

Overall file system structure


Data blocks of a file

Adding a block to a file


From path to inode

cur = 1
For i in  [0 .. n]
    Look for the association [inum, name] in the data blocks of
        the cur dinode such that name is ei
    cur = inum

File creation and deletion

xv6 I/O stack


Main functions of inodes (1/3)

Main functions of inodes (2/3)

Main functions of inodes (3/3)

Open files

File descriptors

What you must remember