L11

Overview

FS provides a convenient interface for using disk. (Disks are essential because they keep data across machine reboots, unlike memory.)
Disk has unique performance characteristics
- Seek+Rotational latency is significant (5~12ms)
- Average disk throughput is 30-60MB/s
- Disk sector size is usually 512 bytes
The FS inteface:
- Hierarchical: organize files into directories. Directories can contain files and subdirectories.
  - The UNIX FS interface: fd=creat("/a/b/c", ..), read(fd,..), write(fd,..), mkdir("/a/d",...),...
- Why hierarchical? Why not use a flat namespace?
FS layout and implementation
How to organize a hierarchical FS on the flat disk?
A simple strawman (from the 70's RT 11 file system)
Designate sector 0 as boot sector, sector 1 as superblock.
Superblock contains disk information (size of disk, size of sector, ...) as well as (location,size) of root dir
Directory contains an array of entries specifying file name to file (location, size).
Root dir starts from sector 2.
Starting from root dir, the FS can traverse the entire tree
Disadvantages of the above layout?
- External fragmentation.
FAT(File allocation table) file system
FAT uses fixed size allocation (e.g. 1KB) to address the external fragmentation problem

FAT keeps a linked list of numbers representing how blocked are chained together

 0      1     2                   2^12+2
+------+-----+-------------------+-------------------------------------------------
|boot  |super| FAT               |
|sector|block|                   |
+------+-----+-------------------+-------------------------------------------------

Let = FAT[a]
- n = FREE , meaning block is free
- n = END, meaning n is the last block of the current file
- or else n means the next block is n
Directory entry contains file name, first block number, size
How to allocate a file of size x?
Advantages and disadvantages of FAT?
- No more external fragmentation, but incurs internal fragmentation
- Space overhead (4 byte pointer per 1KB block, even if it's not used)
- Long list traversal time for finding nth block of a file?
FFS file system
- Fixed size disk blocks (same as FAT)
- A tree-like pointer structure to keep track of blocks in a file (reduce O(n) seeks to O(log n))
- Free block bitmap to keep track of idle blocks (less space overhead, 1-bit-per-block)

I-node based implementation

Inode is a data structure (typically 128 bytes) containing basic information (size, permission, mode, type and the number of links pointed to it) about a file or directory.
Inode contains a number of direct block pointers (e.g. 12) and in-direct pointers.

  the i-node data structure
  +--------------------+
  |size,               |
  |permission,         |
  |mode,               |
  |type,               |
  |nlink               |
  |...                 |
  +--------------------+
  |direct pointer      |
  |--------------------|
  |direct pointer      |
  |...                 |
  |--------------------|
  |1-indirect pointer  |
  |--------------------|
  |2-indirect pointer  |
  |--------------------|
  |3-indirect  pointer |
  +--------------------+

(approximate) disk layout of an i-node based FS
0      1     2                   
+------+-----+--------------+------------+----------------------------------+----------------------------
|boot  |super| data block   | inode      | inode table                      |  data blocks
|sector|block| free bitmap  | free bitmap| i.e. an array of i-nodes         |
+------+-----+--------------+------------+----------------------------------+-----------------------------

Hard links: multiple directory entries point to the same inode
Implementing hard links: keep a field (nlink) in inode to keep track of the # of pointers to it. To delete a file, do unlink("/home/jinyang/c") to decrease the inode's link count. When link count reaches zero, the inode is considered free.
Advantages of hard links:
- Provides synonyms to files, e.g. link("/d1/f1.txt", "/d2/f1.txt")
- Supports "robust" renames, e.g. rename("/d1/f1.txt", "/d2/f1.txt")
  1. increase nlink count
  2. write new entry
  3. delete old entry
  4. reduce nlink count

Hard links are not allowed across directories. Why?
Symbolic links: a special file that contains the pathname of the link destination.
- allows linking of directories and linking of files across file systems
FS performance optimizations
Disk is much slower than processor. To improve performance, we must reduce disk requests and avoid seeks as much as possible.
How?
- Caching: keep previously read disk blocks in memory (buffer cache) to reduce future reads from disk
- Delayed writes and batching: modify cached blocks in memory and delay flushing dirtied cache blocks to disk. When flushing, do so in batches of blocks.
When performing (multiple) reads and writes, OS must decide on the order of the read/write requests issued to disk (disk schedule)
Reality: disk seek time is shorter for disk sectors that are close together
First-come-first-server and shortest-seek-time-first do not offer good tradeoffs
Elevator scheduling: satisfy requests in one direction according to shortest seek time. Change direction once running out of requests.
- Circle scan: one way elevator. When running out of request, restart from beginning as opposed to changing direction. Makes sense because disk rotates in one direction only
FS crash recovery
FS essentially keeps a big data structure on disk.
FS data structure must satisfy certain invariants for consistency (FS becomes corrupted if invariants are violated). e.g.
- Every block is used for exactly one FS type.
- Every data block is used by only one file
- NO referenced blocks are marked free
- All non-referenced blocks are marked free
- All referenced blocks are initialized
- ...
Challenging to maintain FS invariants because
1. computer can crash any time
2. dirty blocks are cached in memory
Preparation question: what happens during "rm /D/a"
1. modify direcotory D's dir block to remove a's entry
2. modify D's i-node to update mtime, length
3. modify i-node bitmap to indicate a's i-node is now free
4. modify block bitmap to indicate a's data blocks are now free
What happens during a crash? (Let's assume first each dirty block is immediately written to disk upon modification)
Example inconsistency:
- writes 1.2. happened, but not 3.4. (consequence: freed i-node and disk blocks are "lost").
What's the "fix"? Use an offline FS recovery tool such as fsck
1. fsck descends the FS tree
2. Remembers allocated i-nodes and blocks
3. Re-initialize free i-node and block bitmaps according to step 2
4. Check other invariants e.g. every data block is used by one file, file length matches number of blocks etc.
Caching of dirty blocks potentially makes things worse. Same "rm /D/a" example, now OS keeps dirtied blocks in memory for writing to disk later.
Example inconsistency:
- 3.4. are written to disk, but not 1 and 2!!
- If "echo hello > b" is performed, the i-node of a could be re-used for b
- Consequence: both a and b point to the same data blocks with content "hello"! Such inconsistency is not even detectable by fsck!!
Solutions for robust crash recovery
- Careful ordering of writes (e.g. refer to FFS' soft update algorithm)
- Journaling: keep a write-head log of file system modification operations to ensure atomicity.
For each high level operation, write a journal transaction in the log that consists of
- A start marker
- A list of modified data blocks (consisting of modified i-node tables, free bitmaps, actual data etc.)
- COMMIT_RECORD
  - If commit record is present in the log, the transaction is considered complete.
Make sure the transaction record in the log is written to disk before flushing dirtied blocks of the transaction to disk. Will the opposite order work?
To recover, OS copies blocks of completed transactions to disk. When recovery completes, erase transaction records.

Lec 11: File Systems

Overview

FS layout and implementation

FS performance optimizations

FS crash recovery