# HW: advanced system 1
###### tags: `Course`
此筆記之網址: https://hackmd.io/@nckuoverload/ADSYSHW1
### 1. When executing the Microsoft Windows command XCOPY, what are the service functions needed from the file system? Please list the functions and give your reason.(20 points)
- 首先會從根目錄的 inode 開始讀取找到 block number。再讀取 block number 並找到下一層資料夾的 inode。重複至找到檔案為止。
- 在建立檔案時，寫入至 block，並且會在 parent inode table 註冊該 block 。
微軟在複製上面主要提供了三種指令，分別是 COPY, XCOPY, ROBOCOPY
題目中的 XCOPY 指令和 COPY 指令相似，功能也和 Linux 上的 `cp` 相似，所以可以使用 `strace cp a b` 來探討。
- open()
`open()` 由系統提供，在執行過程中會比對權限等操作。並且在 `do_file_open()` 時會確認是否為創建文件的操作 `if (!(open_flag & O_CREAT)) `如果是創建的話則沒必要繼續往下操作可以直接返回，如果不是的話才會繼續往下將內容映射至記憶體上。因此整個操作包括 read 和 write 都可以藉由 `OPEN()` 來完成。可以參考第 123 行。
```linux=98
set_tid_address(0x7f87de3e8ad0) = 24837
set_robust_list(0x7f87de3e8ae0, 24) = 0
rt_sigaction(SIGRTMIN, {0x7f87dd167b50, [], SA_RESTORER|SA_SIGINFO, 0x7f87dd173390}, NULL, 8) = 0
rt_sigaction(SIGRT_1, {0x7f87dd167be0, [], SA_RESTORER|SA_RESTART|SA_SIGINFO, 0x7f87dd173390}, NULL, 8) = 0
rt_sigprocmask(SIG_UNBLOCK, [RTMIN RT_1], NULL, 8) = 0
getrlimit(RLIMIT_STACK, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
statfs("/sys/fs/selinux", 0x7ffc8d0f1650) = -1 ENOENT (No such file or directory)
statfs("/selinux", 0x7ffc8d0f1650) = -1 ENOENT (No such file or directory)
brk(NULL) = 0x1ef2000
brk(0x1f13000) = 0x1f13000
open("/proc/filesystems", O_RDONLY) = 3
fstat(3, {st_mode=S_IFREG|0444, st_size=0, ...}) = 0
read(3, "nodev\tsysfs\nnodev\trootfs\nnodev\tr"..., 1024) = 503
read(3, "", 1024) = 0
close(3) = 0
open("/usr/lib/locale/locale-archive", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=5058288, ...}) = 0
mmap(NULL, 5058288, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7f87dcc8f000
close(3) = 0
geteuid() = 1000
stat("useless", 0x7ffc8d0f14d0) = -1 ENOENT (No such file or directory)
stat("./file.o", {st_mode=S_IFREG|0775, st_size=8384, ...}) = 0
stat("useless", 0x7ffc8d0f1260) = -1 ENOENT (No such file or directory)
open("./file.o", O_RDONLY) = 3
fstat(3, {st_mode=S_IFREG|0775, st_size=8384, ...}) = 0
open("useless", O_WRONLY|O_CREAT|O_EXCL, 0775) = 4
fstat(4, {st_mode=S_IFREG|0775, st_size=0, ...}) = 0
fadvise64(3, 0, 0, POSIX_FADV_SEQUENTIAL) = 0
mmap(NULL, 139264, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f87de3ef000
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\2\0>\0\1\0\0\0000\4@\0\0\0\0\0"..., 131072) = 8384
write(4, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\2\0>\0\1\0\0\0000\4@\0\0\0\0\0"..., 8384) = 8384
read(3, "", 131072) = 0
close(4) = 0
close(3) = 0
munmap(0x7f87de3ef000, 139264) = 0
lseek(0, 0, SEEK_CUR) = -1 ESPIPE (Illegal seek)
close(0) = 0
close(1) = 0
close(2) = 0
exit_group(0) = ?
```
### 2. Why is the number of sectors per cluster in FAT must be power of 2? (10 points)
主要是為了避免空間上的浪費。
電腦主要都是二進制形式 (也有 3-bit OS)，假設今天以 6 和 8 為例，6 和 8 都需要至少三個位元來呈現，如果僅僅使用 6 會造成空間的浪費。檔案存取時又是以 cluster 為單位。
### 3. Develop a program that implements the following function:(20 points)
- (A) Input: an ASCII character string s consisting of letters or digits
- (B) Output: if the file or sub-directory named s exists, then display either “s is a file” or “s is a sub-directory” according to the type of s; display “s does not exist.” otherwise.
程式碼如下所示:
1. 首先使用兩個 set 結構來協助處理，set 結構並不會儲存重複的元素
2. 再透過 `os.walk()` 來遍歷目前路徑下所有的資料夾和檔案
3. 最後再查看 set 內是否有一開始輸入的元素
```python
1 import os
2
3 print("This program will traverse the path")
4 inputString = input("input the string \"s\": ")
5 fileSet = set()
6 dirSet = set()
7
8 for root, dirs, files in os.walk("."):
9 dirSet.add(os.path.basename(root))
10 for i in files:
11 temp = i.split('.')
12 fileSet.add(temp[0])
13
14 if (inputString in fileSet):
15 print(inputString + " is a file")
16 elif( inputString in dirSet):
17 print(inputString+" is a sub-directory")
18 else:
19 print(inputString+" does not exist")
```
執行結果:
### 4. In C programming language, data type FILE is used to access files, (A) where is FILE defined? (B) is the definition O/S specific or file system specific? Why?
(A): stdio.h 可以參考自 wikipedia
(B): O/S
Linux 系統因有 VFS 的設計，所以基本上要存取檔案都是透過 VFS 來存取，而 VFS 會將檔案系統抽象化掛載。因此基本上所有 `FILE` 的操作都是透過 kernel 和 VFS 來執行。下面可以粗略地分析 `open` 在 Linux Kernel 的操作。
首先建立一個簡單的 `.c` 並編譯，內容僅有單存的 `FILE *fp; fp=fopen();`，之後再透過 `strace` 來觀察系統會使用到哪些系統服務來執行。系統會使用 `open()` 來協助 C 語言中 `fopen` 的指令操作，因此針對 `open()` 和其 man page 來探討問題。
1. 呼叫 `open` 系統服務
2. 經過一系列呼叫後會呼叫到 fs/open.c 中的 SYSCALL_DEFINE3()
3. 之後會先比對系統為 32-bit 或是 64-bit，若為 64-bit 則會以大檔案的方式開啟
4. 接下來流程主要是執行 `do_sys_open()`
5. 首先會使用 `build_open_flag()` 得到 dentry 和 inode，並透過變數 `fd` 來當作該檔案的描述子 (descriptor)
6. 接著使用 `getname()` 來獲得一個 `filename` 結構的回覆並分配至 kernel memory。至此完成 fd 的獲取。
7. 透過 `do_file_open()` 來開啟檔案，主要是透過`nameidata_to_filp()` 開啟，並且返回 fd。至此已完 `do_sys_open()` 的操作。
8. 最後會將 fd 映射（映射至一開始宣告的記憶體位址）。
基本上第 7 步驟才是主要的開啟檔案的程式，前面的步驟主要在搜尋檔案或是獲得一些設定值 (R,W,RW...)，第 7 步驟中 `nameidata_to_filp` 是主要開啟檔案的方式，根據描述是直接對硬碟做 I/O （使用 `remap_pfn_range()` 將檔案映射至 memory），該函式的返回值為一 file 結構的指標。
實作程式碼:
```Cpp
#include <stdio.h>
#include <stdlib.h>
int main(){
FILE *fp;
fp=fopen("hello.txt","r");
return 0;
}
```
`strace ./file.o`
[1] wikipedia: https://zh.wikipedia.org/wiki/Stdio.
[2] open() man page: http://man7.org/linux/man-pages/man2/open.2.html
[2] `open()` source code: https://elixir.bootlin.com/linux/latest/source/fs/open.c
[3] 參考自這篇 https://ithelp.ithome.com.tw/articles/10185030
### 5. Design and conduct an experiment to demonstrate how the file system selects a free storage unit (sector, cluster, block, node, etc) to be allocated to a file, such as unused unit (if any) first, last freed first, least recently used first, first unused first, next unused first, or others? Please describe: the operating system and file system used, the steps in the operating procedure, the principles of operation, the results and discussion. (similar as an experiment report) (40 points)
OS: Ubuntu 18.04
FS: ext4
Sector size: 512 (logical) / 4096 (physical)
**小結論**
透過實驗一可以得知， ext4 檔案系統的配置方式為 first fit，並且會進行對齊，因為第一次連續配置三個 4 block 大小的檔案時，並不是從一開始的空閑位置進行配置，而後配置 1 block size 的檔案時，會從一開始還有空間的部分進行配置。
實驗一和實驗二的差別在於配置的檔案系統內是否有建立資料夾，因此實驗二的檔案放置並不是完全的 first fit。
實驗過程
實驗一：
1. 使用 `lsblk` 指令來觀察目前的配置情況，該次實驗會使用配置在 sdi8 並且掛載在 `/media/ext4` 的資料夾來完成。
2. 使用 `dumpe2fs /dev/--` 指令可以看到該指定硬碟的配置情況，並且透過 Free blocks 來得到目前未使用的 block。
3. 使用 `seq 3000 > 1 2 3` 指令來配置檔案，每個檔案會佔用 4 block 大小的空間。
4. `rm 1` 移除第一個檔案，並且空出 4 block。
5. `seq 1000 > 1_1` ( 1000 大約 1 block, 3000 會佔用 4 blocks) 配置一個 1 block size 的檔案，並且觀察他的行為。
6. `seq 1000 > 1_2` (繼續佔用了 block 在最前面的的分) 再配置 1 block size 的檔案，會發現繼續配置在最前面的部分。
7. `seq 3000 > 4` 配置一個 4 block 大小的檔案，該檔案會從 32804 開始配置 4 block。
8. `seq 1000 > 1_3` 配置最後一個 1 block 大小的檔案，該檔案會配置在 32803。
實驗二：
使用 dumpe2fs 指令，僅支援 ext4 系列的檔案系統。
1. 先列出目前路徑的 inode 和 目前掛載的硬碟資訊
`ls -l -i -a | sort -n -k 1`
`lsblk`
2. 使用 `dumpe2fs` 查看目前的訊息
32733 free blocks
Free blocks: 32802-33279, 33281-65535
使用 `seq 10240 > se` 會寫入 1~10240 到檔案 se 中
之後配置變化變為如下圖
32720 free blocks
Free blocks: 32802-33279, 33281-33791, 33805-65535
總共使用了 14 個 block 配置在 33791 - 33805 區間
繼續配置 3 個一樣大小的檔案
32681 free blocks
Free blocks: 32828-33279, 33281-33791, 33805-34303, 34317-65535
Free blocks: 32828-33279, 33282-33791, 33805-34303, 34317-65535
Free blocks: 32828-33279, 33295-33791, 33805-34303, 34317-65535
3.
`rm se2` (seq 10240 > se2)
32680 free blocks
Free blocks: 32802-32814, 32828-33279, 33295-33791, 33805-34303, 34317-65535
釋出了 32802-32814 的區間
4.1 再配置一個 大於 14 個 block 大小的檔案
32532 free blocks
Free blocks: 32802-32814, 32976-33279, 33295-33791, 33805-34303, 34317-65535
配置在 33828-32975 的區間
4.2 配置一個小於 14 個 block 大小的檔案，查看是否會配置在 32802-32814 的區間
僅使用到 1 block，並且配置在 38014
4.3 配置 3 個 1 block 大小的檔案
分別配置在 32802, 32803, 33295
4.4 配置 1 個 2 block 大小的檔案
配置在 32812, 32813
4.5 配置 1 個 3 block 大小的檔案
若是配置在 32976-33279 中任意區間內則代表該檔案系統為 best-fit，若配置在 32804-32811 則代表為 first-fit
最後是配置在 33805-33807 區間
4.6 將位於 32804 之前的檔案擴充成 3 block 大小
原本位於 32802 的空間會被釋出，並且重新配置至其他地方。
結論:
使用 ext4 檔案系統於 USB 上，但寫入的方式並不固定，似乎並不是連續寫入並且也不會把空間用盡，會盡量保持一些拓展空間給予檔案擴充。
Sign in with Wallet
Connect another wallet