## File system
synchronizes access: 同步訪問

file system 的幾個議題 1. disk layout 2. performance (disk are slow) 3. buffer cache 4 concurrency (併發查找文件路徑) 5. crash safety (crash 之後如何復原文件系統)

open read 和 write 是常見訪問file system 的 api，open("pathname",write_o...)，可已通過pathname創建文件，並給予文件描述符，write可通過文件描述符對文件進行寫入，同時須紀錄偏移量，讓下次write時能繼續寫入上一次的位置。

xv6 的文件系統(軟體)有七層
1.**Disk layer**:讀取vitual disk **(SSD)** 的資料，物理地址在0x10001000。

2.**buffer cache** layer:緩衝區緩存disk的block，確保不會出現synchronizes access同一塊block的情形出現(**加鎖**)，一組block是buffer的data structure單位。
3.**logging layer**:確保更新能一次完成(涉及多個block)，並且在面對crash時，更新操作是atomic的，要馬就一次更完，不然就不更。
4. **inode layer**: 紀錄每個文件，並給予一組i-number，且紀錄該文件對應的多組block，一組block有16組inode的結構體。
5. **directory layer**: inode的其中一種，紀錄每個節點對應的inode和路徑。
6. **pathname layer**: 可以通過路徑名去尋找檔案。
7. file descriptor: 通過file descriptor 去抽象資源，例如pipe and device and file，使開發者更好操作他們。


### disk的物理地址劃分 (disk沒用vitual map的技術)

note: emmc 就是當作disk在使用的。

1. 第零個block用於作業系統的啟動(bootloader)，初始化硬件，並將disk某些資料燒寫進memory。
2. 第一個super block用於儲存文件系統的大小，inode log 的block數量等訊息，會透過mkfs的程式，進行文件系統啟動。
3. bit map則是記錄data 的block大小。

sector 是 512 bytes
block 是 1024 bytes

**inode block**
一個inode block能有1024/64個inode的data structure。
一個inode是一個data struct，佔64byte，其結構如下:
有inode的type，指向inode的link，size，還有block number，0~11直接指向第幾個bn，bn12則是一個間接bn表，用一個block紀錄256的block的bn位置。

inode 的 data structure


inode 也有一組類似cache 的東西

**directory layer 的實現**

當傳入一個directory :舉例y/x;會先透過inode中的rood folder的inode(inode#1)，從inode block number查找y folder的inode number，再跳到y folder 的 inode 查找 x 的 inode number，最後會透過directory的 data structure 回傳 inode number 和 檔名。


**log layer 原理**
log 原理就是把寫入disk的data先寫入log(log完成 commit 後，就變成disk的一部分)，一個sector為一個單位，預防發生system crash。

也就是log data 資料寫入完成後，才會修改log head，代表整個atomic的操作，如果 log head 是0，reboot system 就不會執行寫入 disk。

log 也是通過buf進行寫入操作的，buf 是存在memory的一種data structure，也是實際寫入disk的基本單位。


將log的data寫到disk的對應位置:

log實際寫入disk的過程:

begin_op 等待所有thread write完成，接著從cache buffer寫入log的 buffer:

end_op則會進行commit。


commit:

但xv6的效率不是非常高，為了使用log保證安全性，使用大量重複的write操作。

log 會遇到的兩個問題 eviction(驅逐)和log size

eviction是當cache容量超過時，會驅逐最後使用的buffer，如果log的某些buffer被驅逐，會破壞log寫入的atomic，透過bpin解決，使對應buffer的bufcnt增加，不會被驅逐。

log size 則是因為log 的大小有限，如果write一次寫入大量的block，會將block進行拆分，分成多次block進行寫入。

最後則是concurrant的問題，當多個thread寫入log時，需進行處理，在log size 未滿時，會對所有thread進行紀錄，當所有thread都完成寫入操作時(outstanding=0)，才會進行commit。

如果超出 log size，則會進入sleep，直到commit完成，log size清空。


## EXT3

**asynchronizes**
ext3是一種linux 使用的log技術，他相比xv6的system call，使用asynchronizes的技術，system call 在寫入buffer之後就return ，不需要等待寫入log的時間，和進行commit的動作，透過asynchronizes的操作，提高system call 的速度。

但須注意資料是否有完成儲存，如果發生crash或之類的操作，有可能導致數據丟失，可以使用flush(fd)等類似操作，直到系統寫入disk 才進行return。
**batching**
ext3透過batching的技術，他可以更好的執行absortion，也就是同一個block的inode能一起寫入，而不是根據system call，多次寫入同一個block，只為修改不同inode。
另外大量寫disk的操作，可以根據disk位置，由上到下寫入，提高寫入速度。

**concurrency**
能讓system call達到parallism，不需要等待其他system call。

並寫log 的接收不影響之前log 寫進disk中，達到i/o的concurrancy，也就是log 接收buffer -> log commit -> write disk -> freed，能併發執行。

而ext3 在 buffer commit 時，會複製當前 block 的 buffer，執行寫入硬碟，不影響後續操作。

**ext3 的 code:**
通過start得知syscall的number，並通過get獲取修改的block的cache並進行修改。
系統每過幾秒，會考慮是否commit。

**ext3 commit 步驟**
1.commit之後的new sysytem call進入阻塞。(性能缺陷但保護system call 的 atomic)
2.等待未完成的outstanding system call 完成修改。
3.open new transaction ，阻塞的system call 可以運行。
4.把當前transcation 所有 dirty block(透過get()獲取)，寫入log 的 cache。
5.將資料寫入log的disk。
6.等待4.5完成。
7.commit record on log (類似log head吧?)。
8.等待寫完
9.將buffer寫回對應的location
10.將log那塊disk釋放。

**linux log 示意圖:**
是一個環狀結構，如果T10要分配但容量不足時，需等待T7的transaction完成釋放。

ext3 就是xv6的log的transaction分成好幾個部分，藉此獲取併發性。

ext3 有 journal 和 ordered 兩種狀態，journal狀態，就是上面講的先把block寫入log在寫入disk，ordered則是直接寫入文件的disk，log則是繼入些改後的inode等修改訊息，就不用寫兩遍，速度比較快。

## Lab filesystem

**lab :Large files**
擴增原來的inode，原來的像這樣

最後新增一個雙指標的indirect block ，讓inode 大小擴增到 256*256，像這樣:

首先是修改dinode(inode in disk)的結構體:
原來的NDIRECT是12拿其中一個做為雙指標block的空間，不然disk裡面資料結構的大小是固定的。
創建NININDIRECT大小是256*256，同時修改MAXFILE的大小變成 11 + 256 + 256*256。


修改buffer 中的 inode 結構體:

修改bmap(): (用來返回block的地址) 參考上面，當ip->addr為空時，通過balloc創建一個disk block，在通過bread進行讀取到在buffer就讀buffer沒有就從disk讀取。
同樣原理繼續創建雙重block，創建完的block要把那個buffer寫回log，不然會出錯。

些改itrunc()，釋放創建的file的block: 同樣參考上面即可。

**lab : symlink**
symlink 創建一個system call 用來進行軟鏈接，用一個path 連接其他的link，目標的link不一定要存在。

首先創建一個system call int symlink(char *target,char* path):
path 是 軟鏈接，target 則是目標鏈接

在inode中添加新的type: T_SYMLINK，表示為軟鏈接

在file_control的header添加新的狀態，O_NOFOLLOW，代表不使用軟鏈接到target，而是直接連接。

system call func:

target 和 path 利用argstr讀取。
檢查inode，軟鏈接不能存在

接著使用create創建一個新inode，create時會獲取對應inode的lock，需要手動release，create時inode type 改為T_SYMLINK。

使用writei func 將target 寫入inode 的 block ，最後釋放鎖。

修改open func :
如果syscall open 時遇到軟鏈接，須前往真正的target，depth用來儲存深度，因為軟鏈接尋找超過10需自行停止。
使用迴圈，當inode type 是 symlink時繼續尋找，且 omode 不能是 O_NOFOLLOW
使用readi尋找target地址，需釋放inode的lock。
並透過namei()，使用path 去尋找對應inode。
剩下就是迴圈下去即可。