# file implementation
[TOC]
## File-System Structure
### 基本分類
:::success

我們會在這邊看到 file系統(**OS跑到 disk 整個過程**) 是如何儲存在 disk
:::
:::info
- ==I/O Control== consists of ==device drivers==, special software programs ( often written in `assembly` ) which communicate with the devices by reading and writing special codes directly to and from memory addresses corresponding to the controller card's registers. Each controller card ( device ) on a system has a different set of addresses ( registers, a.k.a. ports ) that it listens to, and a unique set of command codes and results codes that it understands.(**machine code to assemble that we can control device**)
:::
:::info
- The ==basic file system== level works directly with the device drivers in terms of retrieving and storing <font color= "red">raw blocks of data</font>, without any consideration for what is in each block. Depending on the system, blocks may be referred to with a single block number, ( e.g. block # 234234 ), or with head-sector-cylinder combinations.
:::
:::info
- The ==file organization module== knows about files and their <font color= "red">logical blocks</font>, and how they map to <font color= "red">physical blocks</font> on the disk. In `addition` to translating from **logical to physical** blocks(**ch8**), the file organization module also maintains the list of free blocks, and allocates free blocks to files as needed.
:::
:::info
- The ==logical file system== deals with all of the meta data associated with a file ( UID, GID, mode, dates, etc ), i.e. everything about the file except the data itself. This level manages the directory structure and the mapping of `file names` to `file control blocks`, FCBs, which contain all of the meta data as well as block number information for finding the data on the disk.(**mapping the name to find data on disk**)
:::
### main fuction
- 
:::success

1. I/O transfer
2. data stroage
- data 單位:
- logical: block(size 會 change不是固定的)
- phsycial: sector(512bytes to 4K)
:::
:::success

3. data 儲存方式
- Linear list file names with pointer to the data block
- simple to program
- time-consuming to execute
- FAT32(micosoft) and NTFS(UNIX)

- Linear list with `hash` data structure.

- decreases directory search time
- collisions: situations where two file names hash to the same location
- fixed size
- B-trees

- XFS, NTFS, ext4
- Scaling to terabyte/petabyte filesystems
:::
:::success
- Layered file system
- file system (system call process)
- 
:::
### ON Disk Structure
**這同時也是一個順序 disk 存儲順序**
### IN Memory Structure
**open file & read file**

### Virtual File system
**user 不用去擔心mounting 等問題(VFS 在上單一編輯就好)**
:::info

- the VFS in Linux is based upon four key object types:
- The **inode** object, representing an individual file(api)
- The **file** object, representing an open file.
- The **superblock** object, representing a filesystem.
- The **dentry** object, representing a directory entry.
:::
## 二、Free Space Management

Disk allocation/free space 單位是以 block 為主。

1. Bit Vector：用一組 bits 來代表 blocks 配置與否，一個 bit 對應一個Block。
- 

- 優點：Simple，且易於找到連續可用空間 (即找到連續的 0)
- 缺點：bit vector 儲存佔用 memory 空間，所以此法不適用於大型 disk

2. Link List：用 link list 將 free block 串接，形成一個 AV List。
- 

優點：加入/刪除 block 容易
缺點：效率不佳。因為在找尋可用區塊時，需從頭檢視此串列，I/O time 過長 (檢視一個 block 就須做一次 I/O) 。

3. Combination (組合法，Grouping) ：向量加上 link list。取某個可用區塊記錄其它可用區塊之編號。若此區塊不足以容納所有的 free block 編號，則再以其它區塊記錄並用 link 串連。

- 優點：加入/刪除 block 容易，可迅速取得大量可用區塊。
- 缺點：效率不佳，I/O time 過長。
- 

4. Counting：適用於連續區塊較多之情況。在一個 free block 中，記錄其後的連續可用區塊數目 (含自已)。
- 

- 如果連續區塊數目夠多，則 link list 長度可大幅縮短。

## 三、Allocation Methods

**1. 連續性配置 (Contiguous allocation)**

- 若檔案大小為 n 個 blocks，則 OS 必須在 disk 上找到 >= n 個連續 free blocks 才能配置。

- 記錄方式 :File Name, Size, Starting Block

- 優點：

1. 可支援 sequential access 及 random access
2. seek time 通常較短 (檔案所佔的連續區塊大都會落在同一個 track 上)

- 缺點：

1. external fragmentation
2. 檔案大小無法任意增/刪
3. 建檔時須事先宣告大小

**2. 連結配置 (Link allocation)**

- 若檔案大小為 n 個區塊，則 OS 必須在 disk 上找到 >= n 個可用區塊即可配置 (不一定要連續)。各配置區塊之間以 link list 做串連。

- 記錄方式 :

File Name, Start Block #, End Block #

- 優點：

1. 沒有 external fragmentation
2. 檔案可任意增/刪空間建檔時無需事先宣告大小

- 缺點：

1. 不支援 random access ：要讀某個檔案的某個區塊時需從頭找起，只支援 sequential access。
2. seek time比 contiguous 配置方式長，非連續性 blocks 可能散落在不同的 track。
3. Reliability 差，若連結斷裂則會資料丟失。

**3. 索引式配置 (Index Allocation)**

- 每個檔案皆會多配置一些額外的 blocks 作為 index blocks，內含各配置的 data block 編號。採非連續性配置方式。

- 記錄方式 : File Name, Index Block #

- 優點 :

1. 沒有 external fragmentation：linked list 的優點
2. 支援 random access 及 sequential access：contiguous 的優點
3. 可任意增/刪空間
建檔時無需事先宣告大小

- 缺點 :

1. index blocks 佔用額外空間：索引區塊佔用 free block 的空間。
2. index block 太小不夠存放一個檔案的所有 block 編號，太大又形成浪費。

- 解決 index block 不夠大的三個方法：

1. 利用多個 index blocks 儲存，且其之間以 link 方式串連。
- 缺點是資料區塊 IO 隨大小線性成長，無法 random access。
2. Multilevel index
- 僅適用大檔案，小檔案不適合 (似 2-level cache table)，當存到小檔案時，有可能 index 的大小會大於檔案。
3. Unix i-Node Structure

**[用心去感覺] Unix i-Node Structure**

有 15 個Pointer，可逐級累加使用。

- 1~12 號指標 : 儲存 data block # (檔案的Block需求 ≤12 個時適用)
- 13 號指標 : 指向 Single-level index
- 14 號指標 : 指向 Two-level index
- 15 號指標 : 指向 Three-level index

**[實例1] FAT (File Allocation Table)**

為 link allocation 的變形。將所有配置區塊之間的 link 及 free block 資訊全部記錄在一個Table(FAT)。FAT集中在磁碟某一個固定位置，或可以將它載入主記憶體內，因此雖然在找尋指標時是循序找尋，但速度相對快很多。若 disk 有 n 個 blocks，則 FAT 有 n 個項目 (不論是Free的還是使用中的Block皆需記錄)。

FAT中的項目資訊：

空白 : 表示 free block。
block # : 有 link 指向此 block，即使用中的 block。

概覽：
MS-DOS 及 OS/2 採用
Physical directory 的記錄方式 : [file name, FAT Index]
block 可完全都存放 data，不像 link Allocation 會有幾個 byte 用來存放連結。
優缺點和 link allocation 差不多。

**[實例2] Extent-Based Systems - ext4**

現代檔案系統使用改良式的 contiguous allocation，例如 ext4。

ext4基本資料：

發布時間：2006年10月10日 (Linux 2.6.28, 2.6.19)
目錄內容：連結串列, hashed B-tree
檔案分配：Extents/Bitmap

Extents-based : Extent 指的是一連串的連續實體 block，這種方式可以增加大型檔案的效率並減少分裂檔案。

Extents 大小不用一樣。
Extents 間採用 sequential access

ext4 引進了 Extent 檔案儲存方式，以取代 ext2/3 使用的 block mapping 方式。ext4 支援的單一 Extent，在單一block為4KB的系統中最高可達128MB。單一 i-node 中可儲存 4 筆 Extent；超過四筆的 Extent 會以 Htree 方式被索引。