simplefs

Structure Overview

+---------------+
|  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       | ----> rest of the blocks
|      blocks   |
+---------------+

simplefs 的架構定義在 simplefs.h 中的 simplefs_sb_info 結構體中，每個 simplefs 檔案系統中包含：

1 個 block 作為 superblock
sb->nr_inodes 個 inode，剩餘數量由 sb->nr_free_inodes 紀錄
數個連續的 block 作為 bitmap，用來紀錄 inode 的使用狀況
sb->nr_blocks 個 block，剩餘數量由 sb->nr_free_blocks 紀錄
數個連續的 block 作為 bitmap，用來紀錄 block 的使用狀況

而 simplefs 中的 inode 會統一存放在 superblock 後的數個 block 中，即上方示意圖中的 inode store 區段。

在 simplefs 中，所有資料都是以 Little Endian 的形式儲存，因此會在存取資料時使用 htole32、le32toh 處理 host 與 Little Endian 間的轉換。

Block and Inode

Block

檔案系統中最基本的儲存單位，在 simplefs 中 block 的大小由 SIMPLEFS_BLOCK_SIZE 巨集定義：

#define SIMPLEFS_BLOCK_SIZE (1 << 12) /* 4 KiB */

不論是 inode, bitmaps 還是 superblock 都是儲存在儲存裝置中，而當需要修改或是讀取這些 block 時，都是透過 buffer_head 相關的 API 進行讀寫，例如在透過 simplefs_create 建立檔案時，會透過 sb_bread 讀取指定的 block 到 buffer 中，然後就可以透過這個 buffer 修改資料，等到要更新資料到儲存裝置上時，再透過 mark_buffer_dirty 標記 buffer 中的資料需要更新到儲存裝置上。

TODO: buffer_head 原理、address_space_operations

Inode

用來表示 inode 的結構體 simplefs_inode 定義在 simplefs.h 中：

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 */
    uint32_t ei_block;  /* Block with list of extents for this file */
    char i_data[32]; /* store symlink content */
};

simplefs_inode 基本上就是 VFS 的 inode 結構體的子集合，只包含權限、大小等必須紀錄在儲存裝置中的資訊，不用耗費額外空間儲存沒使用到的資訊。

但由於 VFS 提供的界面的參數都是 inode 等 VFS 提供的類型，因此 simplefs 還另外使用了另一個結構體 simplefs_inode_info 來輔助：

struct simplefs_inode_info {
    uint32_t ei_block;  /* Block with list of extents for this file */
    char i_data[32];
    struct inode vfs_inode;
};

這個結構體相當於 inode 在記憶體中的快取，會在建立新的 inode 時一併被建立：

(gdb) bt
#0  simplefs_alloc_inode (sb=0x60b7e000)
    at /home/freshliver/tmp/linux/stable/linux-5.12/simplefs/super.c:29
#1  0x00000000600fb34a in alloc_inode (sb=sb@entry=0x60b7e000) at fs/inode.c:234
#2  0x00000000600fc5ee in iget_locked (sb=sb@entry=0x60b7e000, ino=ino@entry=5) at fs/inode.c:1193
#3  0x00000000648b75b4 in simplefs_iget (sb=sb@entry=0x60b7e000, ino=ino@entry=5)
    at /home/freshliver/tmp/linux/stable/linux-5.12/simplefs/inode.c:31
#4  0x00000000648b782e in simplefs_new_inode (dir=dir@entry=0x60a53d78, mode=mode@entry=33188)
    at /home/freshliver/tmp/linux/stable/linux-5.12/simplefs/inode.c:191
#5  0x00000000648b7d4b in simplefs_create (ns=<optimized out>, dir=0x60a53d78, dentry=0x60c1e6c0, 
    mode=<optimized out>, excl=<optimized out>)

透過設定中斷點，可以看到在呼叫 simplefs_new_inode 並取得一個新的 inode 後，simplefs_alloc_inode 也接著被呼叫，而這個函式會透過 kmem_cache_alloc 在記憶體中建立一個 simplefs_inode_info 的物件。

但此時這個結構體中只有 vfs_inode 是有意義的，ei_block 與 i_data 則要等到回到 simplefs_iget 後才會正式從儲存裝置中讀取 simplefs_inode 儲存的資料，然後依據檔案類型指派對應的值。

值得注意的是這個 vfs_inode 的型別不是指向 struct inode 的指標，而在 simplefs_alloc_inode 則是回傳 &ci->vfs_inode 給 VFS 使用，這代表 simplefs 的 inode 物件本體是儲存在這個結構體中。

因此只要 VFS 中的 inode 存在的話，就代表這個結構體的物件也存在記憶體中，因此之後只要透過 SIMPLEFS_INODE（本質上是個 container_of）巨集就可以直接透過 inode 取得這個結構體的物件。

TODO: 這個"快取"會一直留在記憶體中嗎？

kmem_cache 運作原理
https://docs.kernel.org/core-api/mm-api.html#c.kmem_cache_create

而 inode 的相關操作則定義在 inode.c 的 simplefs_inode_ops 與 symlink_inode_ops 兩個 inode_operations 結構體的物件中：

static const struct inode_operations simplefs_inode_ops = {
    .lookup = simplefs_lookup,
    .create = simplefs_create,
    .unlink = simplefs_unlink,
    .mkdir = simplefs_mkdir,
    .rmdir = simplefs_rmdir,
    .rename = simplefs_rename,
    .link = simplefs_link,
    .symlink = simplefs_symlink,
};

static const struct inode_operations symlink_inode_ops = {
    .get_link = simplefs_get_link,
};

以最基本的 .create 為例，建立檔案時會呼叫 simplefs_create，要做的工作依序大致為：

透過目錄的 inode 取得 superblock 與對應的 simplefs_inode_info 物件
呼叫 simplefs_new_inode 建立新的 inode
- 檢查檔案權限以及類型是否支援
- 透過 superblock 檢查是否有剩餘的 inode 與 block
- 取得限制的 inode 編號以及實際對應的儲存空間
- 初始化 inode 的 mode, uid, gid 以及時間資訊
- 根據檔案類型（目錄、symlink、一般檔案）設定 i_op、i_fop 等操作
初始化 block 內的資料
根據目錄當前的檔案數量決定要紀錄在目錄的哪個 extent 的哪個 block 的哪個位置

Inode Bitmap and Block Bitmap

TODO: 相關操作函式說明

File and Directory

File

定義在 simplefs.h 中的 simplefs_file 結構體負責紀錄 inode 與檔名的對應：

struct simplefs_file {
    uint32_t inode;
    char filename[SIMPLEFS_FILENAME_LEN];
};

檔名的長度限制為 SIMPLEFS_FILENAME_LEN 個字元，定義在 simplefs.h 中，實際長度定義為 255。

這個結構體主要是在尋找檔案以及走訪目錄時被使用到，能夠透過這個結構體找到某個檔名對應的 inode 編號，接著再透過 simplefs_iget 找到實際的 inode 編號對應的 inode 結構體的物件。

而實際上紀錄在儲存裝置中的資料則是由 simplefs_inode 結構體管理，其中的 i_blocks 會紀錄該檔案佔用的 block 數量，並透過 simplefs_extent 結構體管理：

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 */
};

每個 extent 都是由數個連續的 block 組成，實際對應到的 block 編號範圍為 \([ee\_start,ee\_start+ee\_len)\)，在分配 extent 時會透過 get_free_blocks 一次取得 8 個連續的閒置 block。

但由於 extent 中的 blocks 用完後可能沒辦法找到與原本 block 相連的閒置 blocks，使得檔案系統需要分配新的 extent 給該檔案，而檔案與其使用的 extents 則是透過 simplefs_file_ei_block 結構體來管理：

struct simplefs_file_ei_block {
    uint32_t nr_files;
    struct simplefs_extent extents[SIMPLEFS_MAX_EXTENTS];
};

TODO: 檔案大小上限

而檔案相關的操作則由 simplefs_file_ops 與 simplefs_dir_ops 兩個 file_operations 結構體的物件管理：

// file.c
const struct file_operations simplefs_file_ops = {
    .llseek = generic_file_llseek,
    .owner = THIS_MODULE,
    .read_iter = generic_file_read_iter,
    .write_iter = generic_file_write_iter,
    .fsync = generic_file_fsync,
};

這個結構體定義了非目錄的檔案的操作，四個操作皆為 VFS 提供的通用函式。

TODO: 四個操作的用途以及被呼叫的時機

// dir.c
const struct file_operations simplefs_dir_ops = {
    .owner = THIS_MODULE,
    .iterate_shared = simplefs_iterate,
};

如同名稱，負責目錄相關的操作，這邊有定義的操作只有 iterate_shared，會被 readdir 等需要走訪目錄的操作使用。

TODO: 除了 readdir 以外的呼叫？shared?

Superblock

定義在 simplefs.h 中：

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
};

而 superblock 相關的操作則是定義在 super.c 的 super_operations 結構體中：

// simplefs/super.c
static struct super_operations simplefs_super_ops = {
    .put_super = simplefs_put_super,
    .alloc_inode = simplefs_alloc_inode,
    .destroy_inode = simplefs_destroy_inode,
    .write_inode = simplefs_write_inode,
    .sync_fs = simplefs_sync_fs,
    .statfs = simplefs_statfs,
};

例如：在掛載檔案系統時會呼叫 simplefs_fill_super 將 superblock 讀入記憶體，然後讀取 root inode 並建立檔案系統根目錄的 dentry。

Make simplefs Filesystem

從 Makefile 中製作 simplefs 映像檔的部份：

MKFS = mkfs.simplefs

IMAGE ?= test.img
IMAGESIZE ?= 200
# To test max files(40920) in directory, the image size should be at least 159.85 MiB
# 40920 * 4096(block size) ~= 159.85 MiB

$(MKFS): mkfs.c
	$(CC) -std=gnu99 -Wall -o $@ $<

$(IMAGE): $(MKFS)
	dd if=/dev/zero of=${IMAGE} bs=1M count=${IMAGESIZE}
	./$< $(IMAGE)

在透過 dd 建立指定大小的映像檔後，需要透過 mkfs.simplefs 進行格式化，而格式化的流程定義在 mkfs.c 中。

首先會透過 fstat 這個系統呼叫取得目標映像檔的資訊，用來檢查大小以及檔案類型。

TODO: if not bdev?

接著就會開始依序分配 superblock、inode store、bitmaps 以及 data blocks：

Superblock

Superblock 會透過 write_superblock 函式分配空間，但在分配空間前要先依序計算一些資訊：

Block 總量：

由於所有資訊都是以 block 的形式儲存，所以直接將所有空間分配給 block 即可，總共會有 \(\lfloor \frac{映像檔大小}{Block\ 大小} \rfloor\) 個 block。
Inode 總量：

由於一個 inode 能夠對應到一或多個 block，所以 inode 數量至少需要與 block 數量相同。
不清楚用途：
```
if (mod)
    nr_inodes += SIMPLEFS_INODES_PER_BLOCK - mod;
```
用來儲存 Inode 的 Block 數量：

由於每個 block 能紀錄的 inode 數量有限，因此需要使用 \(\lceil \frac{Inode\ 數量}{每個\ Block\ 能儲存的\ Inode\ 數量} \rceil\) 個 block 來儲存所有 inode。
Bitmaps：

接著由於各個 block 的使用情形會透過 bitmap 紀錄，因此也需要分配一些空間給 bitmap，實際上需要分配的大小為 \(\lceil \frac{Block\ 總量}{8} \rceil\) 個位元組，換算成 block 數量則需要再除以 block 大小，因此為 \(\lceil \frac{Block\ 總量}{8 \times Block\ 大小} \rceil\) 個。

相似地，紀錄 inode 狀況的 bitmap 則共需要 \(\lceil \frac{Inode\ 總量}{8 \times Block\ 大小} \rceil\) 個 block。
Data Block 數量

由於前面的資訊都需要 block 儲存，所以實際上能用來儲存檔案內容的 block 數量會比 block 總數少：儲存 Inode 所需的 Block 數 + Bitmaps 所需 Block 數 個 blocks。

接著，如同前面 Structure Overview 提到的，這些資訊會填入 simplefs_sb_info 結構體中，而這個結構體則會作為第 1 個 block 被寫入至檔案系統中。

Inode Store

將 superblock 的資訊寫入到第 1 個 block 後，接著會透過 write_inode_store 函式將各個 inode 寫入到 block 中。

在一個全新的 simplefs 中，需要分配的 inode 只有這個檔案系統的根目錄，也就是前面 superblock 部份提到的 root inode，若是沒有這個 root inode 的話，在新增 inode 時連要新增到哪個目錄的 block 中也不知道，這個檔案系統也就沒辦法使用。

而這個 inode 的設定跟一般的目錄的 inode 相似，預設權限為 drwxrwxr-x，而實際用來儲存資料的 block 則是 data block 區段中的首個 block，也就是：

1 (superblock) + nr_bfree_blocks + nr_ifree_blocks + nr_istore_blocks

而 inode store 區段中的其他 inode 則不需特別處理，全部初始化為 0 就可以了。

也因為這個根目錄佔用了一個 inode 以及 block，所以在前面寫入 superblock 的閒置 inode 及 block 數量時，其實就有先扣除了：

sb->info = (struct simplefs_sb_info){
    /*...*/
    .nr_free_inodes = htole32(nr_inodes - 1),
    .nr_free_blocks = htole32(nr_data_blocks - 1),
};

Bitmaps

初始化 ifree bitmap 與 bfree bitmap 分別是由 write_ifree_blocks 和 write_bfree_blocks 兩個函式負責處理。

write_ifree_blocks 會根據 superblock 中設定的 ifree bitmap 所需的 block 數量，將所有未使用的 inode 對應的位元都填入 1 表示可被分配。而由於目前只有分配 root inode，因此除了 inode bitmap 佔用的第一個 block 的第一個位元為 0 以外，其餘 block 皆用 1 填滿即可。

write_bfree_blocks 要做的事也很相似，但是已經使用過的 block 不像 inode 只有一個：

superblock 使用 1 個 block
inode store 使用了 sb->info.nr_istore_blocks
ifree bitmap 使用 sb->info.nr_ifree_blocks
bfree bitmap 使用 sb->info.nr_bfree_blocks
root inode 對應的 block

所以需要比較特別的方法將 0 填入對應的位元：

uint32_t i = 0;
while (nr_used) {
    uint64_t line = 0xffffffffffffffff;
    for (uint64_t mask = 0x1; mask; mask <<= 1) {
        line &= ~mask;
        nr_used--;
        if (!nr_used)
            break;
    }
    bfree[i] = htole64(line);
    i++;
}

每次以 64 位元的變數 line 為單位，透過 for 迴圈從 LSB 開始填入 0，若這個 line 已經填完的話，就寫入 bfree 這個與 block 大小相同的 64 位元整數陣列暫存，直到指定數量的位元都填入 0 後才會將整個 bfree 寫入對應的 block 中。

TODO: 在什麼情況下會超過一個 block? 應該檢查 i 是否 out of range?

Data Blocks

TODO: 尚未實作，應全部填入 0？

Registering and Mounting

Registering and Unregistering

核心模組定義在 fs.c 中，掛載模組時，首先會在 simplefs_init 中透過 simplefs_init_inode_cache 建立 Inode Cache，然後才會呼叫 register_filesystem 將 simplefs 加入到 file_systems 串列中。

而卸載模組則相反，先將 simplefs 從 file_systems 串列中移除後才會將釋放 Inode Cache。

Mounting and Unmounting

Mounting

首先在 Linux 中 mount 是根據不同掛載裝置而有不同的掛載函式，如同 VFS 內所提到三種函式，而在 simplefs 中是選擇使用 mount_bdev() 作為掛載函式，並且利用 simplefs_fill_super 作為初始化 superblock 的函式

struct dentry *simplefs_mount(struct file_system_type *fs_type,
                              int flags,
                              const char *dev_name,
                              void *data)
{
    struct dentry *dentry =
        mount_bdev(fs_type, flags, dev_name, data, simplefs_fill_super);
    if (IS_ERR(dentry))
        pr_err("'%s' mount failure\n", dev_name);
    else
        pr_info("'%s' mount success\n", dev_name);

    return dentry;
}

Unmounting

至於卸載檔案系統則是將 superblock 的資訊給消除掉，主要會利用到 linux/fs/super.c 的 kill_block_super

void simplefs_kill_sb(struct super_block *sb)
{
    kill_block_super(sb);

    pr_info("unmounted disk\n");
}

File page cache and read/write blocks on disk

simplefs 同時提供將 page cache 讀寫和從硬碟上將 block 從檔案系統中寫入至硬碟，而 block 中的資料可以同時包括 superblock, inode 和 bitmaps，而在 simplefs 中如同本章之前所提大約為 4 KB。

struct extent

在了解方法之前，先了解結構體 extent ，結構體 extent 是在較新的檔案系統中才有的結構體，目的是為了解決處理大型檔案的問題，比如說在檔案系統如 bfs 就是直接對 block 進行操作，如以下程式碼

static int bfs_get_block(struct inode *inode, sector_t block,
			struct buffer_head *bh_result, int create)
{
	unsigned long phys;
	int err;
	struct super_block *sb = inode->i_sb;
	struct bfs_sb_info *info = BFS_SB(sb);
	struct bfs_inode_info *bi = BFS_I(inode);

	phys = bi->i_sblock + block;
	if (!create) {
    ...

上述情況會有什麼問題，那就是在處理大型檔案比如說超過 10 MiB 的檔案，以一個單位只有 4 KiB 的 block 來處理，那勢必會耗費大量時間，但是透過結構體 extent ，一次會分配 8 個 block 來處理檔案不管是要寫入或是讀取，以減少每次都要對每個 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  |      extent 94 
+-----------------------+         | ee_start  = 94 |---> +--------+
                                  |----------------|     |        |     
                                1 | ee_block  = 8  |     +--------+
                                  | ee_len    = 8  |      extent 99
                                  | ee_start  = 99 |---> +--------+ 
                                  |----------------|     |        |
                                2 | ee_block  = 16 |     +--------+
                                  | ee_len    = 8  |      extent 66 
                                  | ee_start  = 66 |---> +--------+
                                  |----------------|     |        |
                                  | ...            |     +--------+
                                  |----------------|  
                              341 | ee_block  = 0  | 
                                  | ee_len    = 0  |
                                  | ee_start  = 0  |
                                  +----------------+

Get blocks from file system

如何將 file system 中的資料映射到要儲存在硬碟上的 block，要知道在 simplefs 中運用了 superblock，inode 等結構體來記錄一個檔案系統的資訊，所以一開始使用下面兩個定義來取得 superblock 和 inode 的資訊

#define SIMPLEFS_SB(sb) (sb->s_fs_info)
#define SIMPLEFS_INODE(inode) \
    (container_of(inode, struct simplefs_inode_info, vfs_inode))

而為了知道檔案要映射到硬碟的哪個區域，simplefs 使用結構體 simplefs_extent 來管理硬碟的起始地址，長度，以及起始 block 的地址，sb_bread 則是透過 superblock 和 inode 來得知檔案的 block 的大小範圍，最後在找到 index 後，利用 iblock 來找出這個檔案在硬碟的 block 編號範圍。

static int simplefs_file_get_block(struct inode *inode,
                                   sector_t iblock,
                                   struct buffer_head *bh_result,
                                   int create)
{
    struct super_block *sb = inode->i_sb;
    struct simplefs_sb_info *sbi = SIMPLEFS_SB(sb);
    struct simplefs_inode_info *ci = SIMPLEFS_INODE(inode);
    ...
    bh_index = sb_bread(sb, ci->ei_block);
    if (!bh_index)
        return -EIO;
    index = (struct simplefs_file_ei_block *) bh_index->b_data;
    extent = simplefs_ext_search(index, iblock);
    ...
}

最後則是靠至著 get_free_blocks 在硬碟中找尋空的位置並且透過 map_bh 將 buffer_head 映射到映射到硬碟上。

...
if (index->extents[extent].ee_start == 0) {
        if (!create)
            return 0;
        bno = get_free_blocks(sbi, 8);
        if (!bno) {
            ret = -ENOSPC;
            goto brelse_index;
        }
        index->extents[extent].ee_start = bno;
        index->extents[extent].ee_len = 8;
        index->extents[extent].ee_block =
            extent ? index->extents[extent - 1].ee_block +
                         index->extents[extent - 1].ee_len
                   : 0;
        alloc = true;
    } else {
        bno = index->extents[extent].ee_start + iblock -
              index->extents[extent].ee_block;
    }

    /* Map the physical block to to the given buffer_head */
    map_bh(bh_result, sb, bno);
...

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.