Tricky issues in file systems
Taylor ‘Riastradh’ Campbell
campbell@mumble.net
riastradh@NetBSD.org

EuroBSDcon 2015
Stockholm, Sweden
October 4, 2015

What is a file system?

I Standard Unix concept: hierarchy of directories, regular files,

device nodes, fifos, sockets.
I Unified API: file descriptors.
I Traditionally unified storage: inodes.
I Directories are sometimes ‘different’: contain metadata

pointers.

File system operations

I creat (open)
I unlink
I linkI rename
I mkdir, rmdir
I read, write, fsync
I (mkfifo, symlink, readdir, &c.)

Reliability properties

I ACID

Atomicity
Consistency
I Isolation
I DurabilityII

I No transactions: only individual operations.

Atomicity

I Operation either happens all at once, or not at all.
I Crash in middle will not leave half-finished operation.

Atomicity: rename

I rename(old,new) acts as if

unlink(new)link(old, new)I unlink(old)II

I . . . but atomic.

Consistency

I All operations preserve consistent disk state.

Isolation

I If process A does rename:unlink("bar")link("foo", "bar")
I unlink("foo")II

I . . . then process B won’t see two links at foo and bar in themiddle.

Durability

I When the sync program returns, whatever file system

operations you performed will stay on disk.

File system states

I File system has one of three states:

clean
dirty
I corrupt (bugs, disk failure, cosmic rays)
II

I Clean flag in superblock:II

0 means known clean
1 means not known whether clean or dirty (or corrupt)

File system states: fsck

I Traditional: file system operations write metadatasynchronously
I Inode updates, directory entry updates
I Every step preserves consistent state but not necessarily clean

state.
I On boot:II

If marked clean, just mount.
Otherwise, fsck -p globally analyzes file system to undo
partially completed operations.

File system states: fsck example

I Inode block allocation — need space to append to file:Find block in free list.
Mark block allocated.
I Assign block to inode.
II

I If crash after block allocated, before block assigned:

fsck -p scans all inodes
finds all assigned blocks
I frees unassigned but allocated blocks
IIFile system states: fsck to fix corruption

I fsck (without -p) also tries to fix corrupted file systems
I (Doesn’t always work)

Logging

I Physical block logging:Write blocks serially to write-ahead log(not synchronously)
I After committed to log, write to disk
I After committed to disk, free space in log
I After crash, replay all committed writes in log
II

I Faster to recover from crash (but not corruption): replay log

is quick scan, not global analysis
I . . . but isn’t usually quite enoughLogging

I Logical block logging:Write logical operations serially to write-ahead log
After committed to log, perform operations on disk
I After committed to disk, free space in log
I After crash, replay all committed operations in log
II

I More complex to implement
I But usually necessary at least a little

Physical vs logical

I NetBSD FFS WAPBL, write-ahead physical block logging
I Actually, composite of physical and logicalPhysical vs logical: block deallocation

I Deallocate blocks from file, e.g. on rm
I Reuse blocks immediately? No!
I Reallocated block write might happen before log write!
I Logical log entry: deallocate block
I Physical log entry: change inode to not point at block
I When physical log committed, then commit logical log

Reliability assumptions

I Atomic disk sector writes
I Disk write ordering
I Disk write cacheDisk encryption

I Threat model: attacker reads (possibly several) snapshots ofdisk (e.g., airport security)
I (Why several? Reallocated disk sectors, especially in SSDs.)
I 1–1 plaintext/ciphertext disk sector mappingI

512 bytes of plaintext → 512 bytes of ciphertext

I No defence against malicious modification of disk!
I Easy to preserve atomicity of disk sector writes, write

ordering, &c.

Disk authentication

I Threat model: attacker can write malicious data to disk
I Expand each disk block with secret-key MAC?
I 512 bytes of user data → 528 bytes of disk sector?

Splits file system’s idea of logical disk sector across two
physical disk sectors
I Atomicity? Nope!
II 496 bytes of user data → 512 bytes of disk sector?
INot nice for file system!

File system authentication

I Rewrite tree of pointers-with-MAC all the way to the root?
I ZFS can do this; FFS, not so much.

Data/metadata write ordering

I Traditional FFS:
I
I

Synchronous metadata writes
Asynchronous data writes (roughly)

I Typical logging FFS:
I
I

Serial metadata writes
Asynchronous data writes

I No write ordering between data/metadata!

Garbage data appended after write?

I Allocate free block
I Write data to block (A)I Write inode to point at new block, increase length (B)I What if B happens before A?
I What if crash between B and A?
I Now file has whatever data was in free block!

Performance and concurrency

I Coarse-grained locking: easy, slow
I Want per-object locking

RenameI Four different objects to lock!
I Any pair of them may be the same!
I Need consistent lock order.

Rename: orphaned directory trees/home/home/foo//usr/var% mv /home /home/foo/bar

Lock order?

I Traditional in FFS: flail randomly?
I FreeBSD: wait/wound locks, without priorities — livelock!
I ZFS: complicated! (Ask me after. Also broken.)
I Linux and NetBSD: ancestor-first, one rename in flight,deadlock-freeSuspend

I Need for taking snapshot (unless, e.g., log-structured)
I Need for unmount
I Prevent all operations:II

Block new operations.
Wait for existing ones to drain.

I In NetBSD: called fstrans.

Suspend: reader/writer lock?

I Can use recursive reader-writer lock: file system operations

take read lock, suspend takes write lockI Slow! Point of contention for every file system operation.

Suspend: pserialized reader/writer lock

I Better: use passive serialization.
I Reader creates per-thread structure, touches no global state,

unless suspend in progress
I Writer: marks suspend in progress, waits for all per-thread

structures to drain

Questions?

I campbell@mumble.net