simplefs - HackMD

# simplefs contributed by < `Nahemah1022` > ## 背景知識 -- Linux 檔案系統 > file system is an organization of data and metadata on a storage device. ![](https://i.imgur.com/EVMNuqn.gif) 檔案系統之間的行為都不盡相同，因此 Liunx 採用了 virtual file system (VFS) 的架構，讓應用程式能夠用統一的方法去操作每種不同的檔案系統，在實作新的檔案系統如 simplefs 時也只要遵照 VFS 介面規範即可。事實上檔案系統只是一個操作檔案、目錄的「傳遞介面」，其職責只限於在 VFS 的規範下提供一套能夠正確操作檔案、目錄的管道，並紀錄相關的 metadata 資訊；這些檔案的實際格式和作用，則由應用程式負責，並非檔案系統的職責。 > 這也是為何 UNIX 風格的作業系統 (如 Linux) 對於 `.exe` 和 `.txt` 一類的副檔名不特別重視，後者由應用程式決定該如何識別和運用。 ### 註冊檔案系統至 VFS 使用下方的 API，即可建立、移除一個檔案系統 ```cpp #include <linux/fs.h> extern int register_filesystem(struct file_system_type *); extern int unregister_filesystem(struct file_system_type *); ``` 其中 `file_system_type` 應包含如下資訊： ```cpp struct file_system_type { const char *name; int fs_flags; struct dentry *(*mount) (struct file_system_type *, int, const char *, void *); void (*kill_sb) (struct super_block *); struct module *owner; struct file_system_type * next; struct list_head fs_supers; struct lock_class_key s_lock_key; struct lock_class_key s_umount_key; }; ``` - `name` : 即檔案系統的名稱，如 ext2、simplefs - `fs_flags` : 用來標示檔案系統狀態的 flags - `mount` : 檔案系統實體被建立時會呼叫的 callback function，其必須要 return root dentry - 其中通常會呼叫 `mount_bdev()`，來將檔案系統掛載至 block device - `kill_sb`：檔案系統被 shut down 時呼叫的 callback function ### Superblock [superblock object](https://github.com/torvalds/linux/blob/master/include/linux/fs.h#L1419) 中有整個檔案系統所需要的 metadata，也是負責操作 inode 的地方，以下為在 simplefs 的 superblock 中有使用到的欄位： - `s_maxbytes` : 即 max file size - `s_ops` : 定義 VFS 會對 superblock 操作的 [super_operations](https://github.com/torvalds/linux/blob/master/Documentation/filesystems/vfs.rst#struct-super_operations) 內容 - `s_magic` : 代表檔案系統的 magic number :::warning [magic number](https://github.com/torvalds/linux/blob/master/include/uapi/linux/magic.h) 是在 Linux 中用來識別檔案系統 format 的機制，將一段特別設計的 byte code 放在 superblock 的欄位中，使得 Linux 可以藉由讀取 magic number 來識別裝置上檔案系統的 format 。 ::: ### inode > inode 是 index node 的縮寫 inode 是 Linux 檔案系統中的一種資料結構，用來存放檔案系統中 file 的 metadata 資訊，也是檔案與資料之間執行讀取、寫入等操作的中間介面。 :::warning 上述的 file 不單指 regular file，事實上 Linux 中有許多如與檔案系統相關的檔案、目錄、symbolic link、甚至 [pipe/fifo](https://man7.org/linux/man-pages/man7/pipe.7.html) 和裝置節點 (device node) 一類都會以 file 的形式存放，也都會有其對應的 inode 存在。 > 這也是為何 "file" 不該翻譯為「文件」，漢語「文件」沒有上述 file 的擴充的意涵，但若用「歸檔」來思考 Linux 對 "file" 的處置，就合理多了。 ::: 以下擷取部份 simplefs 中有使用到的 [inode object](https://github.com/torvalds/linux/blob/master/include/linux/fs.h#L611) 欄位： - `i_ino` : 即 inode 的編號 - `i_ctime` : inode 建立 (create) 的時間 - `i_atime` : inode 最後一次被存取(access)的時間 - `i_mtime` : inode 最後一次被修改(modify)的時間 - `i_mode` : 該檔案的存取權限 (permission) - `i_op` : 定義可使用的的 [inode_operations](https://github.com/torvalds/linux/blob/master/Documentation/filesystems/vfs.rst#struct-inode_operations) 內容 - `i_fop` : 定義可使用的的 [file_operations](https://github.com/torvalds/linux/blob/master/Documentation/filesystems/vfs.rst#struct-file_operations) 內容 - `i_mapping->a_ops` : 定義可使用的 [address_space_operations]([https://github.com/torvalds/linux/blob/master/Documentation/filesystems/vfs.rst#struct-file_operations](https://github.com/torvalds/linux/blob/master/Documentation/filesystems/vfs.rst#struct-address_space_operations)) 內容 :::info address_operations 是用來定義在檔案系統中，記憶體 (cache) 與實體儲存空間 (disk) 相關的機制 ::: ### dentry > dentry 是 directory entry 的縮寫 dentry 是在檔案實體與 inode 之間的介面，用來追蹤檔案與目錄之間的 hierarchy 結構，每個 dentry 會將一個 inode number map 至一個 file，並紀錄其父目錄。 ![](https://i.imgur.com/8kOIy8D.gif) ### 掛載檔案系統（Mounting） :::info 掛載 (mount) 是在 Linux 中，用以掛載檔案系統並連接 (attach) 到儲存裝置，使得 user 能夠透過檔案系統中的操作來建立檔案與目錄。以下將解說如何建立一個儲存裝置，並將 ext2 檔案系統載入其中，這些操作與在 simplefs 專案中 Makefile 與 test script 的方法相同。 ::: #### 1. 建立並初始化一個儲存裝置在接下來的操作中，我們採用的儲存裝置並不是一個實體的 [block device](https://en.wikipedia.org/wiki/Device_file#Block_devices) （如 CD、USB 隨身碟），而是建立一個 [loop device](https://en.wikipedia.org/wiki/Loop_device) 來作為掛載的標的，因此先用 `dd` 命令建立一個一般的檔案 ```shell $ dd if=/dev/zero of=test.img bs=1k count=10000 10000+0 records in 10000+0 records out 10240000 bytes (10 MB, 9.8 MiB) copied, 0.0171363 s, 598 MB/s ``` - `dd` 命令將參數 `if` 指定對象中的內容複製到參數 `of` 指定的對象中，複製的資料長度由後方 `bs` 、 `count` 參數決定 - `if` 所指定的 `/dev/zero` 也是一個 Linux 內建的 pseudo device，其內容皆為 0 ，要將內容初始化為全 0 時常會這麼使用 - `of` 所指定的 `test.img` 單純是一個 regular file，稍後會使用到現在獲得了一個內容全為 0 的檔案 `test.img`，我們藉由 `losetup` 命令，將檔案操作對應於 pseudo device `/dev/loop0` ```shell $ losetup /dev/loop0 test.img ``` 如此一來，稍後就可以將他當作一般的 block device 來操作了 #### 2. 對儲存裝置建立檔案系統的存取要建立一個 ext2 檔案系統，可藉由 `mke2fs` 命令，直接如下執行即可 ```shell $ mke2fs -c /dev/loop0 10000 ``` 若是要建立 simplefs 檔案系統，則執行以下命令即可，同樣是會將檔案系統連接 (attach) 至儲存裝置上 ```shell $ ./mkfs.simplefs test.img ``` #### 3. 掛載檔案系統 ```shell $ mkdir /mnt/point1 $ mount -t ext2 /dev/loop0 /mnt/point1 ``` 如此一來，`/mnt/point1` 就會是一個格式為 `ext2` 、儲存裝置是 `/dev/loop0` 的檔案系統了若要掛載 simplefs 檔案系統也是類似的方法，如下 ```shell $ mount -t simplefs -o loop test.img /mnt/point1 ``` --- ## simplefs 程式解析 :::info 檔案系統是以 kernel module 的形式在 Linux 中執行，但檔案系統的 kernel module 不同於一般 character device 的 kernel module，user application 並不會直接透過 `file_operations` 與檔案系統交流，而是由 VFS 來操作檔案系統中的各個元件。因此在接下來 simplefs 的實做中，大部分的程式碼都是從 `<linux/fs.h>` 中定義的 Linux VFS 介面加以實做，即可完成一個檔案系統。 ::: --- ### 檔案系統架構 simplefs 中以一個 block (4 KiB) 為儲存單位，下方圖示是 simplefs 的 partition layout，以及每個 partition 中能存放的 block 數量 ```c simplefs partition layout +---------------+ | superblock | 1 block +---------------+ | inode store | sb->nr_istore_blocks blocks +---------------+ | ifree bitmap | sb->nr_ifree_blocks blocks +---------------+ | bfree bitmap | sb->nr_bfree_blocks blocks +---------------+ | data | | blocks | rest of the blocks +---------------+ ``` 這樣的 partition layout 是在檔案系統格式化時建立的，也就是 `mkfs.c` 中所執行的內容，以下逐一說明各個 partition 的細節 #### superblock 功能如同一般檔案系統中的 superblock，存放關於整個檔案系統的 metadata 資訊。除了定義在 `<linux/fs.h>` 中 `struct super_block` 結構中的欄位之外，simplefs 的 superblock 還額外紀錄了以下資訊: ```cpp struct simplefs_sb_info { uint32_t magic; /* Magic number */ uint32_t nr_blocks; /* Total number of blocks (incl sb & inodes) */ uint32_t nr_inodes; /* Total number of inodes */ uint32_t nr_istore_blocks; /* Number of inode store blocks */ uint32_t nr_ifree_blocks; /* Number of inode free bitmap blocks */ uint32_t nr_bfree_blocks; /* Number of block free bitmap blocks */ uint32_t nr_free_inodes; /* Number of free inodes */ uint32_t nr_free_blocks; /* Number of free blocks */ #ifdef __KERNEL__ unsigned long *ifree_bitmap; /* In-memory free inodes bitmap */ unsigned long *bfree_bitmap; /* In-memory free blocks bitmap */ #endif }; struct superblock { struct simplefs_sb_info info; char padding[4064]; /* Padding to match block size */ }; ``` 原本 `struct simplefs_sb_info` 只有共 $8 \times 4$ 個 byte 的大小，但為了使 super block 對齊至剛好一個 block 的大小，`struct superblock` 結構中外加了 $4064$ 個 byte 的 padding 欄位。 #### inode store 功能為集中存放所有 inodes 的區塊，在 simplefs 中的 inode 定義如下，每個大小為 72 byte: ```cpp struct simplefs_inode { uint32_t i_mode; /* File mode */ uint32_t i_uid; /* Owner id */ uint32_t i_gid; /* Group id */ uint32_t i_size; /* Size in bytes */ uint32_t i_ctime; /* Inode change time */ uint32_t i_atime; /* Access time */ uint32_t i_mtime; /* Modification time */ uint32_t i_blocks; /* Block count */ uint32_t i_nlink; /* Hard links count */ union { uint32_t ei_block; /* Block with list of extents for this file */ uint32_t dir_block; /* Block with list of files for this directory */ }; char i_data[32]; /* store symlink content */ }; ``` :::warning 其中 `i_blocks` 紀錄的是 inode 自己的 data block + extent blocks 所佔用的總數 ::: 每個 block 都必需要有一個對應的 inode，因此若儲存裝置的大小能分成 $N$ 個 block，就至少需要準備 $N$ 個 inode，而一個 block 最多可以存 $⌊4096 \div 72⌋ = 56$ 個 inode，因此用來存放這所有的 inode 資料的 inode store partition 需要佔用 $⌈N \div 56⌉$ 個 block (即是 superblock 中的 `nr_inodes` 值) 上方 inode 定義中的 union 則代表此 inode 是檔案 or 目錄的兩種型態何者，其值就是代表對應到的 data block 編號。 :::danger 看起來 `simplefs_inode` 跟 `simplefs_inode_info` 兩個結構紀錄的資訊有部份重疊，那為何要刻意分成兩種結構呢？不能只用一方紀錄就好嗎？ - 線索：取得方式不同： - `simplefs_inode_info` 內有紀錄 VFS 提供的 inode 實體，因此可以利用 `container_of` 直接從 inode 找到其對應 `simplefs_inode_info` 的內容 - `simplefs_inode` 沒有紀錄 inode 實體，需要從 inode 的編號 `ino` 回推其所在 address 後才能找到 --- **ANS: 因為 inode 有兩種存在的型態**，分別是在 cache 中、以及在 disk 中 - 當需要操作 inode 中的資訊時，我們必需要透過 `struct inode vfs_inode` 這個 VFS 提供的 inode 實體，才能跟 VFS 介面溝通 - 然而這個 [`struct inode`](https://github.com/torvalds/linux/blob/master/include/linux/fs.h#L611) 結構中有許多欄位是 VFS 要用的，在一個單獨的檔案系統如 simplefs 中並不需要去重複維持這些資訊 - 因此才會分成兩種結構，`simplefs_inode` 是真正用來紀錄 simplefs 中 inode 的進階資訊，而 `simplefs_inode_info` 則比較像是當 inode 資訊需要寫回 disk 時的一個必要資訊複製模板而已，並且當 inode 需要從 disk 讀回 cache 時也必須從 disk 中有存的 `simplefs_inode_info` 裡面的 inode 編號去回推，才能跟 VFS 拿到真正的 `vfs_inode` ::: #### ifree bitmap 一個 inode 的使用登記表，每個 inode 都用一個 bit 表示，使用中的 inode 在表中標記為 `0`，反之則標記為 `1`，若已在檔案系統中使用了 3 個 inode ，則此時的 ifree bitmap 應為如下： ``` 0000111111........ ``` 若 simplefs 中可用的 inode 總數為 $N$，則這個 partition 需要佔用的空間就剛好是 $N$ 個 bit 。 #### bfree bitmap 同上方的 ifree bitmap，但紀錄的是 block data 的使用。 #### data blocks 前面提到的 superblock、inode store 等等 partition 是用來存資料區塊的 metadata，而這裡的 data block partition 則是實際存放 data 的區塊，其大小就是儲存裝置上剩餘的所有空間。整個 data blocks partition 中一樣是切割成 4KiB 一個 block 為單位，每一個 block 可以區分為下方三種使用情境 : 1. 儲存目錄 inode 的內容資訊 : 當 block 被某個 inode 中的 `dir_block` 欄位對應到時，這個 block 將用來儲存整個目錄下的檔案資訊，其結構定義如下: ```cpp #define SIMPLEFS_FILENAME_LEN 28 #define SIMPLEFS_MAX_SUBFILES 128 struct simplefs_dir_block { struct simplefs_file { uint32_t inode; // 檔案的 inode 編號 char filename[SIMPLEFS_FILENAME_LEN]; // 檔案名稱 } files[SIMPLEFS_MAX_SUBFILES]; // 目錄下的所有檔案 }; ``` 其中的 `struct simplefs_file` 中 `filename` 長度是 28 個 byte，加上一個 inode 4 byte，乘上有 128 個 `struct simplefs_file` 總共 $(28+4) \times 128 = 4096$ 個 byte，剛好會是一個 block 的大小 ``` # inode 與 directory data block 對應示意圖 inode +-----------------------+ | i_mode = IFDIR | 0755 | block 123 | dir_block = 123 ----|--------> +-----------+ | i_size = 4 KiB | 0 | 24 (foo) | | i_blocks = 1 | |-----------| +-----------------------+ 1 | 45 (bar) | |-----------| | ... | |-----------| 127 | 0 | +-----------+ ``` 2. 儲存檔案 inode 的內容資訊: 當 block 被某個 inode 中的 `ei_block` 欄位對應到時，這個 block 將用來存 extent block (實際存放檔案內容的地方) 的編號及長度，其結構定義如下： ```cpp struct simplefs_file_ei_block { struct simplefs_extent extents[SIMPLEFS_MAX_EXTENTS]; }; struct simplefs_extent { uint32_t ee_block; /* first logical block extent covers */ uint32_t ee_len; /* number of blocks covered by extent */ uint32_t ee_start; /* first physical block extent covers */ }; ``` 其中的一個 `struct simplefs_extent` 大小是 3 個 `uint32_t` 共 12 byte，乘上有 341 個 `struct simplefs_extent` 總共 $12 \times 341 = 4092$ 個 byte，差不多是一個 block 的大小。 ```cpp # inode 與 file data block 對應示意圖 inode +-----------------------+ | i_mode = IFDIR | 0644 | block 93 | ei_block = 93 ----|------> +----------------+ | i_size = 10 KiB | 0 | ee_block = 0 | | i_blocks = 25 | | ee_len = 8 | +-----------------------+ | ee_start = 94 | |----------------| 1 | ee_block = 8 | | ee_len = 8 | | ee_start = 99 | |----------------| 2 | ee_block = 16 | | ee_len = 8 | | ee_start = 66 | |----------------| | ... | |----------------| 341 | ee_block = 0 | | ee_len = 0 | | ee_start = 0 | +----------------+ ``` :::danger TODO 疑問：在 `simplefs.h` 中為什麼要把 `struct simplefs_extent` 單獨寫在外面，而不是像上面的 `simplefs_dir_block` 跟 `simplefs_file` 一樣，寫成 struct 包在 struct 裡面就好了呢？個人覺得 `simplefs_dir_block` 的寫法較為簡潔好閱讀，應可改為如下： ```cpp struct simplefs_file_ei_block { struct simplefs_extent { uint32_t ee_block; /* first logical block extent covers */ uint32_t ee_len; /* number of blocks covered by extent */ uint32_t ee_start; /* first physical block extent covers */ } extents[SIMPLEFS_MAX_EXTENTS]; }; ``` > 有疑慮就修改程式碼，然後提交 pull request! 程式碼提供給你的主要目的，就是讓你研究和改進，不是拿來背誦的。 > :notes: jserv ::: 3. 儲存檔案內容的 extent block: ```cpp struct simplefs_extent +----------------+ | ee_block = 0 | | ee_len = 200| extent | ee_start = 12 |-----------> +---------+ +----------------+ block 12 | | +---------+ 13 | | +---------+ | ... | +---------+ 211 | | +---------+ ``` --- ### 掛載流程從 simplefs 的 Makefile 與 test script 中可以整理出，simplefs 從編譯到掛載的流程如下： - 編譯 `mkfs.c`，產出執行檔 ```shell $ $(CC) -std=gnu99 -Wall -o mkfs.simplefs mkfs.c ``` - 編譯為 Linux 核心模組，產出 `.ko` 檔 ```shell $ make -C $(KDIR) M=$(PWD) modules ``` - 建立檔案，將其格式化為 simplefs 檔案系統 ```shell $ dd if=/dev/zero of=test.img bs=1M count=50 status=none $ ./mkfs.simplefs test.img ``` - 建立目錄，建立 [loop device](https://en.wikipedia.org/wiki/Loop_device) 儲存裝置後掛載 simplefs 檔案系統 ```shell $ mkdir -p test $ sudo mount -t simplefs -o loop test.img test $ pushd test >/dev/null ``` --- ### 程式內容 #### mkfs.c 此程式與 Linux 的核心模組及 VFS 介面無關，因此可以看到在 Makefile 中的 `simplefs-objs` 中並不包含 `mkfs.c`。將其單獨編譯後會產出執行檔 `mkfs.simplefs` ，功能是將儲存裝置格式化為 simplefs 的檔案系統格式、劃分成上方說明的 partition layout、並對每個 partition 的內容做初始化，下方將逐一描述每個 partition 初始化的流程: - `write_superblock`: 初始化 super block partition，根據儲存裝置的大小、以及檔案系統中各種元件的大小，來計算出各個分區的邊界，以及 `nr_blocks`、`nr_inodes` 等等 metadata 資訊。 :::danger TODO: 疑問不在 data blocks 區塊中的 block (如 superblock、bfree bitmap、inode store 中的 block) 是否也會需要對應的 inode 呢？若不需要，看起來目前分配的 `nr_inodes` 似乎過多 ::: - `write_inode_store`: 初始化 inode store partition，並建立 root 目錄的 inode 並將 `dir_block` 指向 data blocks 中的第一個 block，再將剩餘的 inode blocks 用 `memset` 初始化為 `0` 。 - `write_ifree_blocks`: 初始化 inode free bitmap partition，除了整個 partition 中的第一個 bit 設為 `0` 之外 (因為第一個 inode 確定會保留給 root 目錄使用) ，將其餘所有 partition 中的 bits 全設為 `1` 。 - `write_bfree_blocks`: 初始化 block free bitmap partition，除了前面已經使用掉的 blocks 會設為 `0` 之外，將其餘所有 partition 中的 bits 全設為 `1` 。 - `write_data_blocks`: 內容尚未被使用。 #### fs.c simplefs 核心模組載入時的初始化動作，如註冊檔案系統至 VFS、初始化 inode cache 空間。 #### super.c 定義在檔案系統掛載時的初始化動作，將儲存裝置中的資訊搬移至 kernel space memory 或 cache 中，並定義 `super_operations`: - `simplefs_fill_super`: - 將檔案系統中存放 super block、ifree_bitmap、bfree_bitmap 的 blocks 讀取出來，並在 kernel memory 中 alloc 一份相同的資訊 - 初始化 root 目錄的 inode - `simplefs_alloc_inode`: 在 cache 中 alloc 出 `simplefs_inode_info` 的空間，建立出一個 simplefs 的 inode 後，將其中的 `vfs_inode` return 給 VFS - `simplefs_write_inode`: 將 cache 中 VFS inode 的資訊取出，並將其中 `struct simplefs_inode_info` 有紀錄的資訊寫回儲存裝置中 - `simplefs_sync_fs`: 當 VFS 要將所有 dirty 的資料寫回 disk 時會呼叫，simplefs 此時會將 superblock、ifree bitmap、bfree bitmap 中的所有資訊也寫回 disk 中 - `simplefs_statfs`: 當 VFS 需要取得檔案系統的 statistics 時會呼叫，simplefs 將資訊如實回傳即可 #### inode.c :::warning ⚠️ 必須特別留意，inode 的資訊可以並存於儲存裝置中的 inode store 中、以及 kernel 的 cache memory 中。 ::: - `simplefs_iget`: simplefs 用來取得某編號的 inode 的內部函式，由 VFS 的 `iget_locked` 取得 VFS inode 後 - 若 inode 已經存在於 cache 中，則無須修改直接 return - 若 inode 尚未存在 cache，則要將其從 inode store 中讀取出來後把資訊加上去後 return - `simplefs_lookup`: 當 VFS 需要在目錄中找尋檔案時會呼叫，simplefs 要找到該目錄 inode 對應的 `struct simplefs_dir_block`，並比對其中所有的檔案名稱是否與目標相同，找到後呼叫 VFS 函式 `d_add` 即可 - `simplefs_new_inode` 在 bitmap 中找到一個可用的 inode 編號、以及一個可用的 block 編號，將兩者連結並修改必要資訊後 return inode - `simplefs_create`: VFS 在建立新檔案、目錄、link 時呼叫 - 檢查檔名長度、檔案數量是否符合規範 - 用上方的 `simplefs_new_inode` 建立一個 inode - 將其 inode 編號加入 dir_block 的 file list 中 - setup dentry - `simplefs_unlink`: 當 VFS 要將 link 移除時會呼叫 - 將目錄中的該檔案對應到的 `struct simplefs_file` 結構移除，其後的檔案遞補上來 - 將檔案對應到的 extent blocks 全部移除 - 用 `drop_nlink` 將 link 從 VFS 中移除 - `simplefs_rename`: VFS rename 檔案時會呼叫 - 檢查新檔案是否符合 simplefs 的規範 - 在新目錄中新增新檔案 - 在舊目錄中刪除舊檔案 - `simplefs_link`: - 新增一個 inode 至目標目錄中，標示為 symbolic inode - 將 inode 與 dentry 透過 `d_instantiate` 連接 --- ## 嘗試修改 Readme 中有提到 simplefs 目前存在兩個問題 1. Directory will be full if more than 128 files 2. Fail to support longer filename 會造成上方 1. 的問題是因為 simplefs 中目錄的 inode 只能對應到唯一一個 data block，不像是檔案的 inode 還能透過 extent 去延伸，若放滿了則無法繼續新增檔案 ```cpp struct simplefs_dir_block { struct simplefs_file { uint32_t inode; char filename[SIMPLEFS_FILENAME_LEN]; } files[SIMPLEFS_MAX_SUBFILES]; }; ``` 目前的目錄 data block 如上所示，若能夠在其中新增一個 `uint32_t next_block` 的欄位，採用類似 linked list 的設計邏輯去紀錄當填滿時下一個要使用的 data block 編號，如此一來只要 data blocks 還夠用就能無限制增加檔案的數量了。