- 判斷 Performance 的前提：

要決定一個系統要用哪種 allocation method，需要先判斷這個系統比較多是需要 sequential access 還是 random access

---
# Allocation methods
## Contiguous allocation
<font color = "red">需要事先宣告大小</font>
==support sequential access, random access==
不管是 sequential access 還是 random access，contiguous allocation 只需要一次 access 就能取得一個 block。因為我們可以直接把一個檔案的起始位置放在 memory 裡面，所以我們很容易可以計算任何第 i 個 Block 的位址，然後就能直接去讀取那個 block。

- Contiguous allocation 適合 small files

## Linked allocation
==support sequential access==
<font color = "red">沒有外碎、不用事先宣告大小，但有 pointer overhead、reliability 差</font>

降低 pointer overhead 的方法：
把好幾個 blocks 收集成 clusters，以 <font color = "snake">cluster</font> 為單位 allocate。
這個方法可以增加 throughput，因為 seek 次數減少，不過缺點是會有內碎，且 random I/O access performance 降低，因為即使只需要一點點 data，也要 transfer 很大量的 data。

如果是 Linked allocation，我們也可以直接把下一個 block 的位址放在 memory 裡面，

### 變型：FAT

FAT 即 File-allocation Table，是 Linked allocation 的變型，沒有支援 FAT 的話 Linked allocation 對 random access 的 performance 就很差


儲存空間開頭的一部分拿來放一個表，這個表的每個 entry 就是一個 block，表的 index 用 block number 來編

directory 的 entry 放檔案的第一個 block 的號碼，由圖例可以看到第一個 block 的號碼是 217，所以我們到 FAT 的第 217 個 entry，看到裡面的值是 618， 618 是這個檔案在 217 後下一個 block 的號碼，如果要再找到再下一個 block，就重複同樣的步驟，到第 618 個 entry 找到 339 ⋯⋯，重複這樣的步驟可以不斷找到下一個 block 的號碼，直到最後一個 block，最後一個 block 的值會是一個特別的值 ``eof``(end-of-file)

FAT 中，沒有用到的 block 裡面的值會是 0 ，所以如果要 allocate 新的 block，只要到表中找到第一個值是 0 的 block，把原本值是 ``eof`` 的 entry 值改成這個 entry 的號碼，再把這個 entry 的值改成 ``eof`` 就好了

FAT 的問題就是可能會有很多的 disk head seek，disk head 要先移動到開頭讀 FAT ，再去找要找的 block 的位置，最後才去找這個 block，最糟的情況下，每個 block 都要重複找 block 的位置、找這個 block 本身。

好處是<font color = "red"> random access time 降低，但 disk head seek overhead 太高，除非 FAT 有被 cached</font>

> FAT random access 好，是因為可以直接讀 FAT 表來看每個 block 的位置

## Indexed allocation
==support random access==
<font color = "red">沒有外碎、但 pointer overhead 比 linked 還高</font>
> 假設只有用到兩個 block，linked 只需兩個 ptr，但 indexed 仍要 allocate 整個 index block，變成只有兩個 ptr 是 non-NULL

因為每個 file 都要有一個 index block，所以 index block 不能太大，否則浪費太多空間，但又不能太小，否則裝不下足夠的 ptr

解決方法有三種，

:::success
- linked theme
- multilevel index
- combined (結合上述兩種)
:::

### Combined: Unix inode

Combined 例子：Unix inode
> $\rightarrow$ 關於 inode 的背景知識，有需要可先跳到下方。

恐龍列出的 inode 內容包含：

:::info

- user / group identifiers of the file
> Owner UID, group UID
- times of the last modification and access
> 總共有四種類型的 timestamps (ACMD times)：
> 1. ++a++time: access time
> 2. ++c++time: inode change time
> 3. ++m++time: data modification time
> 4. ++d++time: deletion time
- count of the number of hard links (directory entriess) to the file
- type of the file
> type: plain file, directory, symbolic link, character decive, block device, socket
- 15 pointers to the disk blocks containing the data contents of the file
> 前十二個 pointers 指向 direct blocks，也就是說這些 pointers 為「包含 file data 的 blocks」的 addresses；接下來三個為 indirect blocks，分別為 single / double / triple indirect blocks。
:::


> 109 交

### inode

因為 file system 需要 track 每個檔案的 info，像是：

- 這的檔案包含哪些 blocks
- 檔案有多大
- 檔案的 owner 是誰、aceess rights
- 有被 access 或 modify 幾次

上述這些所有跟檔案有關的資訊，我們把它稱作 <font color = "snake">metadata</font>。
> 實際上是 file system 裡面「所有不是 pure user data 的資訊」全部都叫做 metadata。

要存放這些資訊（metadata），檔案系統通常會用一種 structure 叫做 <font color = "snake">inode</font>，而且這些 inode 也需要存放在 disk 上面，所以我們需要為 inode 預留一些空間，這部分空間稱作 <font color = "snake">inode table</font>，也就是 disk 上的一個 inode 的 array。
> - 也正是因為這些 inode 是放在 array 裡，才會有 inode 這個名字，代表著 index node 的簡稱。

> 假設我們將 disk 分成 64 個 blocks，因為 disk 裡大部分的資料都是 user data，所以我們假設 block 8-63 是 (user) data，前面 block 3-7 ，標示 ``I`` 的深灰色處則是五個 block 的 inode table（不過實際上 inode 沒有這麼大，通常只有 128 或 256 bytes）
> 假設一個 Block = 4Kb（常用大小），如果 inode 大小是 256 bytes，一個 Block 可放 $\cfrac{2^{12}} {2^8} = 2^4 =16$ 個 inodes
> 因為我們現在 inode table 佔 5 個 Blocks，所以我們可以放 $16 \times 5 = 80$ 個 inode
> 而 80 就是我們這個 file system 最多可以有的 file 數量
>> 如果我們把同樣的 file system 建在一個更大的 disk 上，我們就可以 allocate 一個更大的 inode table，於是就可以放更多的檔案啦～

有了 data blocks 和 inode 以後，接下來我們還需要的是：

追蹤這些 data blocks 和 inode 是不是已經被使用的方法。

舉例來說像是 ++free list++（指向第一個 free block，接著指到第二個⋯⋯）這邊我們選用的 allocation structure 是 <font color = "snake">bitmap</font>，bitmap 就是很簡單的把對應到的 object 或是 block 標 ``1`` 來表示正在被使用，標 ``0`` 表示 free

> 假設 inode table 和 data region 我們都各用一個 block 來放他們各自的 bitmap（第 1, 2 個黑色的 block，``i`` 代表 inode table，``d`` 代表 data region）

實際上用一整個 block 來存 bitmap 有點浪費，因為一個 block 的大小是 4Kb，等同 $(4 \times 8)\ Kbits = 32 \ K bits$，因為一個 bit 可以拿來表示一個 object / block 的使用狀態，所以我們可以 track 32K 個東西有沒有在用，但我們根本就只有 80 個 inode 和 56個 data blocks XD

不過為了看起來比較簡單，就還是用一個 block 的大小來當例子

最後，還剩下一格還沒有用到的 block，這個 block 就拿來當作 <font color = "snake">Superblock</font>，裡面放關於這個 file system 的各種 info，像是裡面有多少 inodes、有多少 data blocks，或是 inode table 從哪裡開始⋯⋯

> 加上了 superblock （用 ``S`` 代表）

所以有了 superblock 以後，如果我們要 mount 一個 file system， OS 就會先去讀這個 superblock，接著設一些 parameter 的 initial value，接著就可以把 volume attach 到 file system tree了 ！

> 把上述所有東西整理出細節就變成這樣

假設我們要讀第 32 號的 inode，file system 就會先看 inode table 從哪裡開始（此處是 $12Kb$），接著計算 offset，也就是第 32 個 inode 離 inode table 的起始位置有多遠（``32 x sizeof(inode)`` 也就是 $32 \times 256 \ byte = 8192 byte$），加起來就可以得到 inode 的 byte address 了

算一算我們的 base + offset：

$\rightarrow$ $12 \ Kb + 8192 \ bytes$
$= 12 \ Kb + 2^{13} \ bytes$
$= 12 \ Kb +8 \ Kb$
$= 20 \ Kb$

因此我們只要到 byte address $= 20 \ Kb$ 就能找到第 32 號的 inode
可是！
這裡會有一個問題就是 disk 根本就不是 byte addressable！也就是說，我們不能隨便要存取哪個 byte 就直接去 access 那個 byte，因為 disk 的基本單位是 sector，所以我們只能來算這個 byte address 是在 sector 第幾號：

假設一個 sector 的大小是 512 bytes（一個常用的大小）

$\rightarrow$ $20 \ Kb = 20 \times 1024 \ bytes$

$\rightarrow$ $\cfrac{20 \times 1024}{512} = 40$
即第 40 個 sector

所以為了要得到第 32 號 inode， file system 會 read sector 40

## File Operation

以下 operation 假設：
- file system mounted，因此 superblock in memory
- 其他所有東西（例如 inode, directories）都還在 disk 上

### open()

假設要打開一個檔案叫做 ``bar``
$\rightarrow$ ``open("/foo/bar,O_RDONLY)``

1. 首先 file system 要先 traverse path name 來找到 ``bar`` 的 inode，去取得關於這個 file 的一些基本資訊
> 基本資訊如 permission、檔案大小等等
2. 因為 traversal 必定從 root 開始，並且在 mount 的時候 file system 就知道 root 的 inode number，所以 file system 第一件事就是把含 inode number 2 （root inode） 的 block 從 disk 讀進來
> UNIX file system 的 root inode number 通常是 2
3. 讀進 root inode 以後， file system 就會在裡面找指向 data blocks 的 pointers，這些 pointers 指的 blocks 會包含 root directory 的內容，file system 就從這裡面去找 ``foo``
4. 一旦找到 ``foo``，就會也找到 ``foo`` 的 inode number
5. 接著就是遞迴去 traverse 整個 path，直到找到我們要找的 inode 為止，在這個例子裡也就是找到 ``bar`` 的 inode
6. ``open("/foo/bar,O_RDONLY)`` 的最後一步就是把 ``bar`` 的 inode 讀到 memory
7. 上述完成以後， file system 就會做最後的 permission check，然後 allocate ``fd`` 再 return

### read()

在做完 open() 以後，program 就可以再發 ``read()`` system call 去讀檔案

1. 第一個 ``read()`` 會讀進這個 file 的第一個 block
> offset = 0 除非有用 ``lseek()`` 特別去改
2. 因為要把第一個 block 讀進來，inode 就會去找第一個 block 的位置
3. 也會更新 inode 的 last accessed time
4. 為這個 file descriptor update in-memory 的 open file table
> 
5. 改 file offset，這樣下次 ``read()`` 就可以讀到第二個 block

### write()

跟 ``read()`` 不一樣的是，``write()`` 可能需要 allocate 一個新的 block（除非是要 overwrite 某個計有的 block）
除了把 data 寫到 disk，首先也要先決定要把哪個 block allocate 給這個 file，還有也要更新其他 disk 上的 structure （例如 bitmap, inode）
因此，做一次 ``write()`` 需要五次 I/O

1. read data bitmap，
2. update (write) bitmap 來 mark 新 allocated 的 block as used
3. read inode
4. write inode 標示新 allocated 的 block 的位置
5. 真的寫到 block

---
## Caching

從前一段 file operation 的例子可以看到，這些 operation 每次要做都要花一堆 I/O，造成 performance 變差，因此 file systems 就<font color = "green">用 system memory(DRAM) 來 cache 重要的 blocks</font>

早期的 file system 用 <font color = "snake">fixed size cache</font> 去放這些常用的 blocks，但是 fixed size cache 需要++在 boot time 就 allocated++，可是這樣的做法有點浪費，因為說不定某些時候 file system 就用不到這麼大的空間，而且 file cache 裡用不到的 pages 也不能拿來做其他的用途

因此，現代的 file system 用的是 <font color = "snake">dynammic partitioning</font>，結合 virtual memory pages 和 file system pages 成 <font color = "snake">unified page cache</font>，這樣一來，memory 的分配就比較有彈性，可以根據 virtual memory 和 file system 哪個需要的比較多在不同的時間點去自由分配

## Reference

- 恐龍
- [Operating Systems: Three Easy Pieces 第 40 章](https://pages.cs.wisc.edu/~remzi/OSTEP/)
> 幾乎所有 inode 的內容都出自這裡，是很簡單好懂的線上資源，推薦！這本書的好處是講得非常簡單清晰，基本上沒太多基礎也能讀；缺點是有點過於簡單，還是需要跟恐龍交互參照一下
- The linux kernel: [index nodes](https://www.kernel.org/doc/html/latest/filesystems/ext4/inodes.html#)