1 of 35

Linux Filesystems, FSCK, and Journaling

CS-446/646

C. Papachristos

Robotic Workers (RoboWork) Lab

University of Nevada, Reno

2 of 35

Linux Filesystems, FSCK & Journaling

Filesystems in Linux

Linux Second Extended File System (ext2)

What is the ext2 on-Disk Layout?
What is the ext2 Directory Structure?

Linux Third Extended File System (ext3)

What is the Filesystem Consistency problem?
How to solve the Consistency problem using Journaling?

Virtual File System (VFS)

What is VFS?
What are the key data structures of Linux VFS?

CS446/646 C. Papachristos

3 of 35

Linux Filesystems, FSCK & Journaling

Linux ext2

“Standard” Linux File System

Was the most commonly used before ext3 came out

Uses FFS-like Layout

Each Filesystem is composed of identical Block Groups
Allocation is designed to improve Locality

inodes contain Pointers (32-bit) to Blocks

Direct, Single Indirect, Double Indirect, Triple Indirect
Maximum File Size: 4.1 TB (assuming 4 KB Block Size)
Maximum Filesystem Size: 16 TB (assuming 4 KB Block Size)

On-Disk structures: /linux/ext2_fs.h

CS446/646 C. Papachristos

4 of 35

Linux Filesystems, FSCK & Journaling

Linux ext2 Disk Layout

Locality:

Files in the same Directory are stored in the same Block Group
Files in different Directories are spread among the Block Groups

CS446/646 C. Papachristos

Free Blocks

Bitmap

inode

Table

(fixed-size)

Free inodes

Bitmap

Superblock: Contains description of the basic Size and Shape of this Filesystem�

Note: Duplicated in all Groups for corruption

Block Group Descriptor Table: Contains description for each Block Group of this Filesystem (Location of Block Bitmap, inode Bitmap, inode Table, # Free Blocks,�# Free inodes, # Directories)�

Note: Also duplicated in all Groups for corruption

1 Block

n Blocks

5 of 35

Linux Filesystems, FSCK & Journaling

Block Addressing in ext2

Multi-Level Indexed Files

CS446/646 C. Papachristos

inode

Metadata

Direct Blocks

Indirect Blocks

Double-Indirect Blocks

Triple-Indirect Blocks

Note 1: �Indirect Blocks: Contain BLKSIZE/4 Block Entries

(32-bit (i.e. 4-Byte) Pointer Size) → 1024 Block Entries

6 of 35

Linux Filesystems, FSCK & Journaling

ext2 Directory Structure

(a) A Linux Directory with 3 Directory Entries (e.g. for Files: colossal, voluminous, bigdir)
(b) After the File voluminous has been removed

CS446/646 C. Papachristos

7 of 35

Linux Filesystems, FSCK & Journaling

Linux ext3

The Consistent Update Problem – Filesystem Consistency

Goal:

Atomically update Filesystem from one Consistent State to another

What is the meaning of “Consistent State”?

Challenge:

An update (even of a single Block) may require modifying multiple Sectors
But the Disk Hardware only provides Atomic write of one Sector at a time

CS446/646 C. Papachristos

8 of 35

Linux Filesystems, FSCK & Journaling

Linux ext3

Review: File I/O Path (Reads)

Filesystem uses Read Buffer Cache to speed-up I/O

read() from a File

Check if Block inside Read Buffer Cache
If yes, return Block
If not, read from Disk,�insert into Read Buffer Cache and return it

CS446/646 C. Papachristos

Disk

Block NOT in Cache

Block IN Cache

Leave Copy in Cache

1

2

Buffer Cache

(Main Memory)

Case:

9 of 35

Linux Filesystems, FSCK & Journaling

Linux ext3

Review: File I/O Path (Writes)

Filesystem uses Write Buffer Cache to speed-up I/O

write() to File

Write is Buffered in Memory – “Write-Back”

(vs “Write-Through”)

OS decides when to write to Disk
… or User-invoked fsync() System Call

Note:

fflush(): Flush internal Application Buffers (of a FILE *) to OS

fsync(): Flush OS Buffers to Physical Media (Device)

Delaying writes important:

Has implications for Performance
Has implications for Reliability

CS446/646 C. Papachristos

Disk

Delayed Write to Disk

Buffer Write in Memory

1

Buffer Cache

(Main Memory)

2

10 of 35

Linux Filesystems, FSCK & Journaling

Example: File Creation of /a.txt

Initial state:

CS446/646 C. Papachristos

Remember:

#0 used as a NULL value (indicates an inode�does not exist), i.e. there is no inode #0
First inode is inode #1, and is reserved for�recording defective Blocks)

Memory

Disk

(Free)

inodes

Bitmap

inode Table

Data Blocks

(Free)

Blocks

Bitmap

11100

01000

/

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

11 of 35

Linux Filesystems, FSCK & Journaling

Example: File Creation of /a.txt

Read-in to Memory Cache:

CS446/646 C. Papachristos

Memory

Disk

inode Table

Data Blocks

11100

01000

<'.', #2>

<'..', #2>

(Free)

inodes

Bitmap

(Free)

Blocks

Bitmap

/

11100

01000

/

…

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

12 of 35

Linux Filesystems, FSCK & Journaling

Example: File Creation of /a.txt

Modify Metadata and Blocks:

CS446/646 C. Papachristos

Memory

Disk

inode Table

Data Blocks

11110

<'.', #2>

<'..', #2>

<'a.txt', #3>

Dirty Blocks, Memory State and Disk State are Inconsistent: Must write to Disk

(Free)

inodes

Bitmap

(Free)

Blocks

Bitmap

11100

01000

/

01110

/

…

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

13 of 35

Linux Filesystems, FSCK & Journaling

CS446/646 C. Papachristos

14 of 35

Linux Filesystems, FSCK & Journaling

Possible Crash Scenarios

File creation example dirties (at least) 3 Blocks

(Data) Blocks Bitmap (B)
inode for new File (I)
Data Block of Parent Directory (D)

Old and new contents of the Blocks:

B = 01000 B’ = 01110
I = free I’ = Allocated, Initialized
D = {<'.', 2> D’ = {<'.', 2>� <'..', 2>} <'..', 2>� <'a.txt', 3>}

CS446/646 C. Papachristos

Crash scenarios: Any subset can be written

B I D
B’ I D
B I’ D
B I D’
B’ I’ D
B’ I D’
B I’ D’
B’ I’ D’

15 of 35

Linux Filesystems, FSCK & Journaling

One solution: File System Consistency checK (FSCK)

Upon reboot, scan entire Disk to make Filesystem Consistent

Scan for Inconsistencies, e.g. inode Pointers and Bitmaps, Directory Entries and inode reference counts

Advantages

Simplifies Filesystem code
Can repair more than just crashed Filesystems (e.g. Bad Sector)

Disadvantages

Slow (hours-long) to scan large Disks

Checking a 600 GB disk takes ~70 minutes

Cannot fix all Disk Crash Sequences

e.g. File Creation B’ I D’ (i.e. inode not updated) –Can this be fixed?

Not well-defined Consistency

CS446/646 C. Papachristos

16 of 35

Linux Filesystems, FSCK & Journaling

FSCK Example 1:

Automatically fix:

CS446/646 C. Papachristos

17 of 35

Linux Filesystems, FSCK & Journaling

FSCK Example 2:

Automatically fix:

CS446/646 C. Papachristos

18 of 35

Linux Filesystems, FSCK & Journaling

FSCK Example 3:

Defer to admin to resolve:

CS446/646 C. Papachristos

19 of 35

Linux Filesystems, FSCK & Journaling

FSCK Example 4:

Can’t automatically fix:

CS446/646 C. Papachristos

20 of 35

Linux Filesystems, FSCK & Journaling

FSCK Example 4:

C. Papachristos

21 of 35

Linux Filesystems, FSCK & Journaling

Another solution: Journaling

Leverages “Write-Ahead Logging” from Database community

Persistently write Intent-to-Log (or “Journal”), then update Filesystem

Crash before Intent/Journal is written == No-op
Crash after Intent/Journal is written == Redo-op

The process is called “Recovery”

Advantages:

No need to scan entire Disk
Well-defined Consistency

CS446/646 C. Papachristos

22 of 35

Linux Filesystems, FSCK & Journaling

Linux ext3 Journaling

1 – Physical Journaling : Write real Block contents of the update to Log

Four totally ordered steps:

1) Write Dirty Blocks to Journal as a single Transaction (e.g TxBegin, I, B, D Blocks)

2) Write commit Block (containing TxEnd)

3) Copy Dirty Blocks to real Filesystem (“Checkpointing”)

4) Reclaim the Journal Space for the Transaction

2 – Logical Journaling: Write logical record (logical representation of the � intended operation) to Log

“Add Directory Entry F to Directory Data Block D”
Complex to implement
May be faster and save Disk Space

CS446/646 C. Papachristos

23 of 35

Linux Filesystems, FSCK & Journaling

Step 1: Write Blocks to Journal

CS446/646 C. Papachristos

Memory

Disk

Dirty Blocks

/

11110

11100

01000

/

<'.', #2>

<'..', #2>

<'a.txt', #3>

01110

…

Journal

TxB

id=1

11110

01110

/

…

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

24 of 35

Linux Filesystems, FSCK & Journaling

Step 2: Write commit Block

CS446/646 C. Papachristos

Memory

Disk

Journal

Dirty Blocks

11100

01000

/

11110

<'.', #2>

<'..', #2>

<'a.txt', #3>

01110

/

…

TxB

id=1

11110

01110

/

…

TxE

id=1

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

25 of 35

Linux Filesystems, FSCK & Journaling

Step 3: Copy Dirty Blocks to Real Filesystem

CS446/646 C. Papachristos

Memory

Disk

Journal

Dirty Blocks

01110

/

11110

<'.', #2>

<'..', #2>

<'a.txt', #3>

01110

/

…

TxB

id=1

11110

01110

/

…

TxE

id=1

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

26 of 35

Linux Filesystems, FSCK & Journaling

Step 4: Reclaim Journal Space

CS446/646 C. Papachristos

Memory

Disk

Journal

Dirty Blocks

11110

01110

/

11110

<'.', #2>

<'..', #2>

<'a.txt', #3>

01110

/

…

#0

#1

#2

#3

#4

#5

#0

#1

#2

#3

#4

#5

27 of 35

Linux Filesystems, FSCK & Journaling

What if there is a Crash?

Recovery :

Go through Log and “redo” operations that have been successfully committed

What if:

TxBegin but no TxEnd in Log?

TxBegin through TxEnd are in Log, but D (Data Block) not in the Journal. Possible?

Remember: Disk Hardware + Sector Mapping + Scheduling

IMPORTANT: This is why we don’t want to merge Step 2 and Step 1

TxB, I, B, D, TxEnd in Log, everything is Checkpointed in Disk, but the Journal Space has not been reclaimed?

CS446/646 C. Papachristos

Journal

TxB

id=1

I

B

?

TxE

id=1

28 of 35

Linux Filesystems, FSCK & Journaling

CS446/646 C. Papachristos

29 of 35

Linux Filesystems, FSCK & Journaling

ext3 Journaling Modes

Journaling has cost

One write = 2 Disk writes, 2 Seeks

Several Journaling Modes to balance Consistency and Performance:

Data Journaling: Journal all writes, including File Data

Problem: Expensive to Journal Data

Metadata Journaling: Journal only Metadata

Used by most Filesystems (IBM JFS, SGI XFS, NTFS)
Problem: File may contain garbage Data

Ordered Mode: Write File Data to real Filesystem first, then Journal Metadata

Default mode for ext3
Problem: Old File may contain new Data

CS446/646 C. Papachristos

30 of 35

Linux Filesystems, FSCK & Journaling

Virtual File System (VFS)

In older times we referred to “the” Filesystem
Nowadays: many Filesystem types and instances co-exist

Virtual File System:

A Filesystem abstraction layer that supports multiple Filesystem implementations

The VFS specifies an Interface via Function Pointer(s)

A struct of Function Pointer(s) representing Interface Operations�e.g. void (*mkdir) (struct inode *i_this);

A specific Filesystem implements this Interface by binding specific Functions

e.g mkdir_ext2(), mkdir_ext3(), …

VFS dispatches Filesystem operations through this Interface

e.g. my_dir_inode->inode_ops->mkdir(my_dir_inode);

CS446/646 C. Papachristos

31 of 35

Linux Filesystems, FSCK & Journaling

Virtual File System (VFS)

A Filesystem abstraction layer that supports multiple Filesystem implementations

The VFS specifies an Interface�via a struct of Function Pointer(s):

A specific Filesystem implements this Interface by binding specific Functions:

VFS dispatches Filesystem operations through this Interface:

CS446/646 C. Papachristos

void mkdir_ext2(struct inode *i_this) {

i_this->…;

}

inode *inode_init() {

inode_ext2 *new_inode = malloc(sizeof(inode_ext2));

new_inode->inode_ops->mkdir = mkdir_ext2;

return (*inode)new_inode;

}

my_dir_inode->inode_ops->mkdir(my_dir_inode);

void mkdir_ext3(struct inode *i_this) {

i_this->…;

}

inode *inode_create() {

inode_ext3 *new_inode = malloc(sizeof(inode_ext3));

new_inode->mkdir = mkdir_ext3;

return (*inode)new_inode;

}

struct inode_ops {

struct inode *i_this; //inode back-pointer

void (*mkdir)(struct inode *); //interface func

};

32 of 35

Linux Filesystems, FSCK & Journaling

VFS Interface Schematic

CS446/646 C. Papachristos

33 of 35

Linux Filesystems, FSCK & Journaling

Key Linux VFS Data Structures

struct FILE

Information about a File object
Includes current position (File offset Pointer)

struct dentry

Information about a Directory Entry
Includes name + inode#
Contains Pointer to associated inode, i.e. field: struct inode *d_inode;

struct inode

Unique descriptor of a File or Directory
Contains Permissions, Timestamps, Block map (Data)
inode#: integer (unique per mounted Filesystem)
Pointer to Filesystem-specific inode structure, e.g. a struct ext2_inode_info

struct superblock

Descriptor of a mounted Filesystem

CS446/646 C. Papachristos

34 of 35

Next Lecture Reading Preparation

Operating Systems – Three Easy Pieces (https://pages.cs.wisc.edu/~remzi/OSTEP/)

Persistence

48. Distributed Systems

Beginning of Chapter
48.1 Communication Basics
48.2 Unreliable Communication Layers
48.3 Reliable Communication Layers
48.4 Communication Abstractions
48.5 Remote Procedure Call (RPC)

49. Sun’s Network File System (NFS)

Beginning of Chapter
49.1 A Basic Distributed File System
49.2 On To NFS
49.3 Focus: Simple And Fast Server Crash Recovery
49.4 Key To Fast Crash Recovery: Statelessness
49.5 The NFSv2 Protocol
49.6 From Protocol To Distributed File System

CS446/646 C. Papachristos

49.7 Handling Server Failure With Idempotent Operations
49.8 Improving Performance: Client-side Caching
49.9 The Cache Consistency Problem
49.10 Assessing NFS Cache Consistency
49.11 Implications On Server-Side Write Buffering
49.12 Summary

35 of 35

Time for Questions !

CS-446/646

CS446/646 C. Papachristos