# Chap. 11 - File system implementation

> 課程內容 : 清華大學開放式課程 周志遠教授
> 參考書目 : Operating System Concepts (9th), Abraham Silberschatz, Peter Baer, Galvin, Greg Gagne
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## Content
* [File system structure](#File-system-structure)
* [File system implementation](#File-system-implementation)
* [1. On-disk structure](#1-On-disk-structure)
* [2. In-memory structure](#2-In-memory-structure)
* [3. Example: fille open/read/create](#3-Example-fille-openreadcreate)
* [4. Virtual file system](#4-Virtual-file-system)
* [Disk allocation methods](#Disk-allocation-methods)
* [1. Contiguous allocation](#1-Contiguous-allocation)
* [1.1 Extent-based file system](#11-Extent-based-file-system)
* [2. Linked allocation](#2-Linked-allocation)
* [2.1 Example: FAT system](#21-Example-FAT-system)
* [3. Index allocation](#3-Index-allocation)
* [3.1 Linked index scheme](#31-Linked-index-scheme)
* [3.2 Multilevel scheme](#32-Multilevel-scheme)
* [3.3 Combine scheme](#33-Combine-scheme)
* [Free space management](#Free-space-management)
* [1. Bit vector](#1-Bit-vector)

## File system structure
當 I/O 在 memory 與 disk 之間執行的最小單位是 blocks，一個 blocks 由多個 sectors 組成，每個 sectors 的大小通常是 512 bytes。

一個 O.S. 可以支援一個以上的 file system type(Ex: NTFS, FAT32)。File system 的設計有兩個重點

* 提供給 user program 的 interface
* 提供給 physical storage 的 interface

下圖顯示了從 user program 到 disk 的分層結構

<img src="https://hackmd.io/_uploads/SksCHDbckl.png" width=500>

(不同 file system 的差異主要在於 file-organization module)

## File system implementation

### 1. On-disk structure

(1) Boot control block (per partition)
每個 partition 上用來開機並啟動 partition 上安裝的 OS 的資訊(code)，通常是 partition 上的第一個 block，如果這段為空代表沒有安裝 OS。

(2) Partition control block (per partition)
包含 partition 上的詳細資訊，例如 blocks 的數量，block size，free block list，...等

(3) File control block (per file)
儲存關於該檔案的詳細資訊，例如 permission，size，location of data blocks

(4) Directory structure (per file system)
用來組織 files。

> [!Note]
> 硬碟(disk)上會以每個 partition 為單位做切割，有些 partition 會安裝 OS 有些不會。每個 partition 的 file system 會有 directory structure，directory 會儲存 file control block。當 process 開啟一個檔案後會再將 file control block 載入到 file-open block 中。

<img src="https://hackmd.io/_uploads/BJKIPnMcye.png" width=500>

### 2. In-memory structure

(1) In-memory partition table
當 file system 掛載(mount)到現在的 partition 時，會載入該 partition 的資訊到 memory 之中。

(2) In-memory directory structure
包含最近使用過的 ditectories 資訊(僅載入最近使用過的而不是全部的 directory，因為太浪費空間)，directory 中包含旗下的 filename 與對應的 file control block 等內容。

(3) System-wide open-file table
紀錄所有已開啟的 file 的全局資訊，包含每個檔案的 file control block 的副本。

(4) per-process open-file table
包含該 process 所開啟檔案的區域資訊以及指標(指向 system-wide table 的對應位置)。

### 3. Example: fille open/read/create

(1) 下圖表示 file open 的操作細節

* 由 user 指定 filename 開啟(假設開啟 `a.txt`)
* 從 kernel memory 中尋找 `a.txt` 所屬的 directory，並從中讀取 `a.txt` 的 file control blocks
* 從 secondary storage 中讀取 `a.txt` 的 file control block，裡面包涵 `a.txt` 的 meta data(permission, size, block location, ...)
* 在 memory 中的 system-wide open-file table 紀錄 `a.txt` 的資訊(meta data)
* 在 process 的 open-file table 建立對應的 file pointer 並回傳給 user


> [!Note]
> file open 只會讀取載入檔案的 file control block 到 memory 之中，不會讀取檔案的內容。

(2) 下圖表示 file read 的操作細節

* User 根據 file pointer 從 kernel memory 中的 process open-file table 找到 `a.txt` 在 system-wide open-file table 的對應位置
* 根據 system-wide open-file table 中紀錄的 file control blocks 找到 `a.txt` 在 secondary storage 中的 data blocks
* 透過 I/O 將檔案內容讀取到 memory 中回傳給 user


> [!Note]
> 只有在 read/write 階段才會讀取檔案的**部分**內容到記憶體之中進行修改。

(3) File creation

* OS 分配一塊新的 file control block
* 更新 directory structure
* OS 先從 disk 中讀取對應的 directory structure 並載入到 memory 中，確認路徑是否存在
* 更新 directory structure 的資訊，包含新的 filename 與 file control block
* 檔案關閉後 OS 將更新過的 directory structure 寫回(write back)到 disk 之中

### 4. Virtual file system

Virtual File System (i.e., VFS) 提供一種物件導向的方式實作 file system。VFS 允許不同的 file system 共用相同的 system call interface 讓使用者不用關心底層的實作方式。當使用者使用檔案的操作時 VFS 會調用對應的 file system 的函式來完成使用者的操作


以 Linux VFS 來說定義了 4 種主要物件

* Inode: 對應單一檔案的 meta data(i.e. file control block)
* File object: 對應一個已開啟的檔案資訊
* Superblock object: 對應完整的檔案系統(i.e. partition control block)
* Dentry object: 對應到 directory entry

## Disk allocation methods

Allocation methods 指出 disk 中的 data blocks 要如何分配給 files。有 3 種分配的策略

* Contiguous allocation
* Linked allocation
* Indexed allocation

### 1. Contiguous allocation

每個 file 佔據了一段連續的 data blocks，directory 只要紀錄每個 file 的

* 開始位置(starting blocks)
* 檔案大小(file size)

使得檔案在 disk 的搜索更簡單，只要用計算的就可以找到 每個 file 所佔據的 blocks，不用搜索整個 disk。


Contiguous allocaiton 在 data 的存取上可以使用 sequential access 或 random access。但 contiguous allocation 會遇到兩個問題

* 容易產生 external fragmentation
* File cannot grow
* 當 file 變大時原有的 blocks 可能會不夠用

#### 1.1 Extent-based file system

Extent-based file system 是一種修改過的 contiguous allocation scheme，旨在改善 file grow 的問題。每一次會分配一個 extent 給 file，當 file 不夠用時再分配下一個 extent，並以類似 linked list 的方式接在前一個 extent 的後面。

:::info
Extent 是一個單位量，由多個連續的 blocks 組成。一個 extent 會紀錄

* 開始的 block 位置
* extent 長度
* 下一個 extent 的位置

每個 file 可能包含一或多個 extent。
:::

但使用 extent-based file system 後在資料的存取上 random access 就不會再佔有優勢，因為當需要讀取 file 中的某個 extent 時，還是必須從第一個 extent 開始做搜索，且一樣會有 internal/external fragmentaion 的可能性。

### 2. Linked allocation

每個 file 中的所有 block 都以 linked list 的方式連接，directory 只要紀錄每個檔案

* 開始的 block 位置
* 結束的 block 位置

Linked allocation 的分配會遇到 3 個問題

(1) Only good for sequential-access files
與 extent-based 的方式相同，在資料的隨機存取上同樣需要從頭開始搜索整個 linked list 才能找到指定的位置。且每一次的存取都是一個 disk I/O 的操作，與 contiguous allocation 每次讀取連續的 data blocks 相比會大幅降低速度。

(2) Space require for pointer
每個 block 除了資料外還需要額外的空間(4/512 bytes)儲存指標。

(3) Reliability
一旦某個 linke 遺失，那整個 file 也會隨之崩潰。

#### 2.1 Example: FAT system

File Allocation Table file system(FAT-32) 是一種改善過的 linked allocation，應用在早期的 MS/DOS 或一些嵌入式系統與 USB 隨身碟中。FAT system 有以下特色

* 將所有的 pointer 儲存在一個表格(table)中
* 表格中的每個欄位(entry)大小為 32-bits
* 表格儲存於 disk 中每個 partition 的開頭，並在開機時會將表格從 disk 載入到 memory 中加快讀取速度，改善 random access

以下圖為例，有一個名為 test 的檔案，directory entry 儲存了該檔案的相關屬性(Ex: start position, permission, ...)，另一個表格(FAT)則紀錄了 test 檔案中每個 block 的指標。

* 開始位置 block 217 指向下一個 block 618
* block 618 指向下一個 block 339
* block 339 指向 EOF

<img src="https://hackmd.io/_uploads/B1IeVdb5ke.png" width=400>

### 3. Index allocation

類似 database，讀取資料時不做搜索，只做查表(look-up)。每個 file 會有自己的 file index block，用來儲存該 file 所有的 block 的位置，讀取資料時直接從 file index block 尋找需要的 block number(direct access 的概念)。Directory 會紀錄每個 file 對應的 file index block。

:::info
可視為將 file 所有的 pointer 儲存在 index block 之中。
:::


* 優點
* 容易實作 direct/random access
* 不會有 external fragmentation
* 缺點
* 需要額外空間儲存 index block
* 儲存 index block 的空間大小不容易決定，可能不夠，也可能浪費空間(file 太小/block 太少)
* Linked index scheme
* Multilevel index
* Combined scheme

#### 3.1 Linked index scheme

每個 index block 預留空間儲存指向下一個 index block 的指標。缺點如同前面與 linked 有關的方法一樣，當檔案越大，搜索時間也會越久，降低 random access 的效能。


#### 3.2 Multilevel scheme

類似 multi-level page table 的做法，(以 two-level 為例)第一層的 index block 儲存第二層的 index block 位置，第二層的每個 index block 才會儲存 file blocks。


#### 3.3 Combine scheme

將 multi-level 與 direct blocks 混合使用。


## Free space management

Free space list 會紀錄所有可用(free)的 disk blocks，並在需要時提供給 file 使用。基本上可以將 free space 想成一個 file，此 file 的每個 block 都是空的。有以下幾種存取方式

* Bit vector
* Linked list(same as linked allocation)
* Grouping(same as linked index allocation)
* Counting(same as contiguous allocation)

除了 bit vector 其他都跟前面一樣。

### 1. Bit vector

Disk 中的每個 blocks 會以一個 bits 作紀錄並儲存在 bitmap 之中(一個 array)。

* `bitmap[i] = 0`: 表示 free block
* `bitmap[i] = 1`: 表示 busy block

因為是以 bits 做紀錄， HW 也支援 bit 的操作與運算，所以速度較快。
缺點是需要額外的空間儲存 bitmap，以 1-TB disk/4-KB block size 來說，會有

$$
\cfrac{10^{12}}{4 \cdot 10^3} = 250 \times 10^6
$$
個 blocks。又每個 blocks 需要 1-bit 表示，因此 bitmap 的大小為

$$
\cfrac{250 \times 10^6 \times 1 \ \text{bit}}{8} \approx 32 \times 10^6 \ \text{bytes} = 32\ \text{MB}
$$