Linux 核心專題: simplefs

# Linux 核心專題: simplefs > 執行人: HotMercury, jason50123 ## simplefs 為了探索 Linux VFS (virtual file system) 介面及檔案系統實作機制，我們從無到有撰寫一個運作於 Linux 核心模式中的精簡檔案系統，原始程式碼約一千餘行，支援基本的檔案和目錄處理，同時也考慮到權限和並行處理的議題。本任務預計整合 [jbd2](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html)，使得 simplefs 具備 [journaling](https://en.wikipedia.org/wiki/Journaling_file_system) 特徵。相關資訊: * [開發紀錄-1](https://hackmd.io/@Nahemah1022/rJo1sAtid) * [開發紀錄-2](https://hackmd.io/@fwfly/simplefs) * [開發紀錄-3](https://hackmd.io/@freshLiver/linux-vfs-main/) * [開發紀錄-4](https://hackmd.io/@sysprog/BymZ7EeH3) ## 讓 simplefs 支援 linux v6.8 > [commit fcac769](https://github.com/sysprog21/simplefs/commit/fcac769284e3bbe40019e64e601b6c1e54da9b33) 在 linux v6.8 下編譯。我們發現在新版 kernel 中 makefile 會強迫檢查 `missing-prototypes` 所以必須加上 prototype define 或是在 function 前面加上 `static` ```c $ make simplefs/fs.c:10:16: error: no previous prototype for ‘simplefs_mount’ [-Werror=missing-prototypes] 10 | struct dentry *simplefs_mount(struct file_system_type *fs_type, | ^~~~~~~~~~~~~~ simplefs/fs.c:26:6: error: no previous prototype for ‘simplefs_kill_sb’ [-Werror=missing-prototypes] 26 | void simplefs_kill_sb(struct super_block *sb) | ^~~~~~~~~~~~~~~~ ``` 此專案中有大量 `i_atime` 以及 `i_mtime` 但根據 [commit 12cd440](https://github.com/torvalds/linux/commit/12cd44023651666bd44baa36a5c999698890debb) 可以知道說這個變數從 `v6.7-rc1` 版本開始，為了不讓 user 存取，就更新成 `__i_atime` 和 `__i_mtime`，並提供了相關的 function 來初始化這些變數。 ```c simplefs/super.c:81:34: error: ‘struct inode’ has no member named ‘i_atime’; did you mean ‘__i_atime’? 81 | disk_inode->i_atime = inode->i_atime.tv_sec; | ^~~~~~~ | __i_atime simplefs/super.c:82:34: error: ‘struct inode’ has no member named ‘i_mtime’; did you mean ‘__i_mtime’? 82 | disk_inode->i_mtime = inode->i_mtime.tv_sec; | ^~~~~~~ | ``` ```diff - inode->__i_mtime = cur_time; + inode_set_mtime_to_ts(inode, cur_time); ``` ```diff - inode->__i_atime.tv_sec = (time64_t) le32_to_cpu(cinode->i_atime); - inode->__i_atime.tv_nsec = 0; + inode_set_atime(inode, (time64_t) le32_to_cpu(cinode->i_atime), 0); - inode->__i_mtime.tv_sec = (time64_t) le32_to_cpu(cinode->i_mtime); - inode->__i_mtime.tv_nsec = 0; + inode_set_mtime(inode, (time64_t) le32_to_cpu(cinode->i_mtime), 0); ``` ```diff - cur_time = current_time(inode); - inode->__i_atime = inode->__i_mtime = cur_time; - inode_set_ctime_to_ts(inode, cur_time); + simple_inode_init_ts(inode); ``` ``` simplefs/file.c: In function ‘simplefs_writepage’: simplefs/file.c:101:12: error: implicit declaration of function ‘block_write_full_page’; did you mean ‘block_write_full_folio’? [-Werror=implicit-function-declaration] 101 | return block_write_full_page(page, simplefs_file_get_block, wbc); | ^~~~~~~~~~~~~~~~~~~~~ | block_write_full_folio ``` :::info 根據 [commit 17bf23a](https://github.com/torvalds/linux/commit/d32cdb32b73c4f720f15a966da84635fa2dddedb) 可以知道從 `v6.8-rc1` 版本以後。 `block_write_full_page` 已經由 `block_write_full_folio` 所取代，因此對程式碼做對應的修改。 ::: ``` diff + #if LINUX_VERSION_CODE >= KERNEL_VERSION(6, 8, 0) + static int simplefs_writepage(struct page *page, struct writeback_control *wbc) + { + struct folio *folio = page_folio(page); + return __block_write_full_folio(page->mapping->host, folio, + simplefs_file_get_block, wbc); + } ``` :::info TODO: 理解為什麼要從 `page` 換成 `folio` ::: ## TODO: 研讀 [VVSFS](https://github.com/EngineersBox/VVSFS) 報告 [VVSFS](https://github.com/EngineersBox/VVSFS) 參照 simplefs 的設計，其報告 `Group17_report.pdf` 值得學習，可作為類似 ext2 的檔案系統實作的參照。本專題可學習 [VVSFS](https://github.com/EngineersBox/VVSFS)，彙整之前的開發紀錄，提供今年度 simplefs 的技術報告。可從 [nullfsvfs](https://github.com/abbbi/nullfsvfs) 探討起，說明一個沒有實際功能的檔案系統是如何與 Linux VFS 互動。 ## TODO: 修正 [Issue #20](https://github.com/sysprog21/simplefs/issues/20) > [commit 855c339](https://github.com/sysprog21/simplefs/commit/855c339457b782843a790e1e67e017e9b219dd46) ### problem disk layout 中的 data block 要是有無意義的資訊將會導致，`ls`, `mkdir`, `touch` 等 command 出錯。經過幾次實驗發現問題出自於，`simplefs_file` 讀取邏輯的問題，當使用 `ls` 時會尋找有效的 `simplefs_file_ei_block`(extent block)，再透過 `simplefs_file_ei_block` 找到 `simplefs_file` (紀錄 name 跟 inode) 且終止條件為找到 0, 但如果在分配 file block 時沒有清空，就會發現後面的資訊都是無意義的，因此無法正確執行。 ```c static struct dentry *simplefs_lookup(struct inode *dir, struct dentry *dentry, unsigned int flags){ for (ei = 0; ei < SIMPLEFS_MAX_EXTENTS; ei++) { if (!eblock->extents[ei].ee_start) break; .... } } ``` 以下為 `simplefs_file` 所在的 block layout 可以看到未使用的地方都是亂數，這樣無法正確的分析資料結構，更可能造成無法結束的狀況。 > sizeof(simplefs_file) -> 259bytes ``` 000f9300: 0000 0000 0000 0000 0000 008d 0e00 0000 ................ 000f9310: 695f 6464 0000 0000 0000 0000 0000 0000 i_dd............ 000f9320: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9330: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9340: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9350: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9360: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9370: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9380: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9390: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f93a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f93b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f93c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f93d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f93e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f93f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................ 000f9400: 0000 0000 0000 0000 0000 0000 0000 001e ................ 000f9410: d958 ecb1 cac4 08d3 842b d777 6997 9b48 .X.......+.wi..H 000f9420: dcb6 86b9 0c65 04f2 1da5 38b2 7d1b 4084 .....e....8.}.@. 000f9430: c612 67d9 ecd9 4f14 79d7 8f67 57ad 976b ..g...O.y..gW..k 000f9440: 81dc a28a bffd 2917 8ff8 89af 8f89 4d47 ......).......MG 000f9450: 5bf1 891d 81e7 a3cc 2a34 086d d02d ccc2 [.......*4.m.-.. 000f9460: a224 80ad d4a7 ec06 2f6e cb2d 61fe f28d .$....../n.-a... 000f9470: 8725 17ab 2936 5be2 8154 7dc5 c73b 9615 .%..)6[..T}..;.. 000f9480: d248 0b00 db56 216f 230d af67 ea2d 97fe .H...V!o#..g.-.. 000f9490: 0343 d99c 98cd 3ab2 e005 4177 645d bb2b .C....:...Awd].+ 000f94a0: 5509 d3ee 808f f479 b638 d859 903a 1f7c U......y.8.Y.:.| ``` ### 解決方法 1. 使用 nrfiles 來當作尋找的方式，而不是以 0 來判斷 2. 分配新的 block 時直接清空對應 block 目前採用 2 的方式 *建立一個目錄的流程* `simplefs_create` 建立一個目錄，接下來透過 `simplefs_new_inode` 呼叫 `simplefs_iget` 設定對應的 inode number 以及 extent block 的資訊。所以我們要在這裡將分配到的 block 都清空。 ## TODO: 排除記憶體處理的缺失過往要偵測 Linux 核心模組是否存在記憶體洩漏 (memory leak)，往往仰賴 kmemleak 一類的機制，不過通常需要重新編譯 Linux 核心，現在 [kmodleak](https://github.com/tzussman/kmodleak) 藉由 eBPF 動態安插檢查程式碼到 Linux 核心，於是就可在不用重新編譯 Linux 核心的狀況下，動態檢測指定 Linux module ? ### 使用 kmodleak 基本上照著 github 指示安裝，但是在 `make` 發生錯誤，這是 [#pragma GCC poison](https://gcc.gnu.org/onlinedocs/gcc-3.2/cpp/Pragmas.html) 的錯誤 ``` /usr/include/string.h:506:15: error: attempt to use poisoned "strlcpy" 506 | extern size_t strlcpy (char *__restrict __dest, ``` :::warning 注意要用較新的 [clang](https://apt.llvm.org/)，如 clang-17，適度修改 `Makefile`，以確保使用你安裝的 clang。 :notes: jserv ::: clang version，且也將 makefile 改成對應的版本依然會有錯誤，所以暫時註解掉就可以執行，但應該不能這樣。 ``` Ubuntu clang version 18.1.3 ``` 在 [libbpf-bootstrap](https://github.com/libbpf/libbpf-bootstrap/issues/226) 有找到這個問題的解法，但我還不知道怎麼解然後使用後沒有預期的方式執行，暫時無解，目前猜是要對 kernel 做而外的設定。 ``` BPFTOOL bpftool/bootstrap/bpftool ... libbfd: [ OFF ] ... clang-bpf-co-re: [ on ] ... llvm: [ OFF ] ... libcap: [ OFF ] ``` ``` vm@vm:~/simplefs$ sudo ../kmodleak/src/kmodleak simplefs using page size: 4096 libbpf: prog 'kmodleak__module_load': BPF program load failed: Invalid argument libbpf: prog 'kmodleak__module_load': -- BEGIN PROG LOAD LOG -- 0: R1=ctx() R10=fp0 ``` [issue 53](https://github.com/sysprog21/simplefs/pull/53) 想要解決 memory leak 的問題，因此在底下重現他的實驗 ``` $ sudo ./kmodleak simplefs -v module 'simplefs' loaded module 'simplefs' unloaded 3 stacks with outstanding allocations: 8192 bytes in 2 allocations from stack addr = 0xa33 size = 4096 addr = 0xc2b size = 4096 0 [<ffffffff9284e7e4>] __alloc_pages+0x264 1 [<ffffffff9284e7e4>] __alloc_pages+0x264 2 [<ffffffff928859b1>] alloc_pages_mpol+0x91 3 [<ffffffff92885f14>] folio_alloc+0x64 4 [<ffffffff927b5734>] filemap_alloc_folio+0xf4 5 [<ffffffff927bac5b>] __filemap_get_folio+0x14b 6 [<ffffffff929411f2>] __getblk_slow+0xb2 7 [<ffffffff92941591>] __bread_gfp+0x81 8 [<ffffffffc0710b59>] init_iso9660_fs+0x6b49 9 [<ffffffff928ff674>] iterate_dir+0x114 10 [<ffffffff928fff94>] __x64_sys_getdents64+0x84 11 [<ffffffff92405b73>] x64_sys_call+0x1b43 12 [<ffffffff9361b78f>] do_syscall_64+0x7f 13 [<ffffffff9380012b>] entry_SYSCALL_64_after_hwframe+0x73 208 bytes in 2 allocations from stack addr = 0xffff898c35e6c8f0 size = 104 addr = 0xffff898c1d3add00 size = 104 0 [<ffffffff9285c8a3>] kmem_cache_alloc+0x253 1 [<ffffffff9285c8a3>] kmem_cache_alloc+0x253 2 [<ffffffff9293d6be>] alloc_buffer_head+0x1e 3 [<ffffffff9293ebb5>] folio_alloc_buffers+0x95 4 [<ffffffff92941238>] __getblk_slow+0xf8 5 [<ffffffff92941591>] __bread_gfp+0x81 6 [<ffffffffc0710b59>] init_iso9660_fs+0x6b49 7 [<ffffffff928ff674>] iterate_dir+0x114 8 [<ffffffff928fff94>] __x64_sys_getdents64+0x84 9 [<ffffffff92405b73>] x64_sys_call+0x1b43 10 [<ffffffff9361b78f>] do_syscall_64+0x7f 11 [<ffffffff9380012b>] entry_SYSCALL_64_after_hwframe+0x73 192 bytes in 1 allocations from stack addr = 0xffff898c015ef180 size = 192 0 [<ffffffff9285c55b>] kmem_cache_alloc_lru+0x25b 1 [<ffffffff9285c55b>] kmem_cache_alloc_lru+0x25b 2 [<ffffffff929046e4>] __d_alloc+0x34 3 [<ffffffff9290493a>] d_alloc+0x1a 4 [<ffffffff92907c7a>] d_alloc_parallel+0x5a 5 [<ffffffff928f2b0c>] __lookup_slow+0x5c 6 [<ffffffff928f2e0c>] lookup_one_unlocked+0x9c 7 [<ffffffff928f2ebd>] lookup_positive_unlocked+0x1d 8 [<ffffffff92aa673d>] debugfs_lookup+0x5d 9 [<ffffffff92aa679f>] debugfs_lookup_and_remove+0xf 10 [<ffffffff9285fd69>] debugfs_slab_release+0x19 11 [<ffffffff927fee5c>] kmem_cache_destroy+0x11c 12 [<ffffffffc070c625>] init_iso9660_fs+0x2615 13 [<ffffffffc0710fe9>] init_iso9660_fs+0x6fd9 14 [<ffffffff925f6943>] __do_sys_delete_module.isra.0+0x1a3 15 [<ffffffff925f6af2>] __x64_sys_delete_module+0x12 16 [<ffffffff92406320>] x64_sys_call+0x22f0 17 [<ffffffff9361b78f>] do_syscall_64+0x7f 18 [<ffffffff9380012b>] entry_SYSCALL_64_after_hwframe+0x73 done ``` 接著使用 [issue 53](https://github.com/sysprog21/simplefs/pull/53) 會變成以下的輸出 ``` vm@vm:~/kmodleak/src$ sudo ./kmodleak simplefs using page size: 4096 Tracing module memory allocs... Unload module (or hit Ctrl-C) to end module 'simplefs' loaded module 'simplefs' unloaded 2 stacks with outstanding allocations: 584 bytes in 1 allocations from stack addr = 0xffff8f20e070c248 size = 584 0 [<ffffffff94e5ceb3>] kmem_cache_alloc+0x253 1 [<ffffffff94e5ceb3>] kmem_cache_alloc+0x253 2 [<ffffffff95b94632>] radix_tree_node_alloc.constprop.0+0xb2 3 [<ffffffff95b96277>] idr_get_free+0x1e7 4 [<ffffffff95b7ab3b>] idr_alloc_u32+0x7b 5 [<ffffffff95b7ac94>] idr_alloc_cyclic+0x54 6 [<ffffffff94fbac9a>] __kernfs_new_node+0xaa 7 [<ffffffff94fbc4c6>] kernfs_new_node+0x56 8 [<ffffffff94fbe919>] __kernfs_create_file+0x29 9 [<ffffffff94fbfa94>] sysfs_add_file_mode_ns+0x74 10 [<ffffffff94fc0cd2>] create_files+0x92 11 [<ffffffff94fc0f20>] internal_create_group+0xc0 12 [<ffffffff94fc10c3>] sysfs_create_group+0x13 13 [<ffffffff94e5e240>] sysfs_slab_add+0x1f0 14 [<ffffffff94e6029e>] __kmem_cache_create+0x3e 15 [<ffffffff94dff198>] kmem_cache_create_usercopy+0x178 16 [<ffffffffc08395d9>] init_iso9660_fs+0x25c9 17 [<ffffffffc084901f>] init_iso9660_fs+0x1200f 18 [<ffffffff94a019be>] do_one_initcall+0x5e 19 [<ffffffff94bf4380>] do_init_module+0xc0 20 [<ffffffff94bf6281>] load_module+0xba1 192 bytes in 1 allocations from stack addr = 0xffff8f20c17599c0 size = 192 0 [<ffffffff94e5cb6b>] kmem_cache_alloc_lru+0x25b 1 [<ffffffff94e5cb6b>] kmem_cache_alloc_lru+0x25b 2 [<ffffffff94f04d74>] __d_alloc+0x34 3 [<ffffffff94f04fca>] d_alloc+0x1a 4 [<ffffffff94f0830a>] d_alloc_parallel+0x5a 5 [<ffffffff94ef319c>] __lookup_slow+0x5c 6 [<ffffffff94ef349c>] lookup_one_unlocked+0x9c 7 [<ffffffff94ef354d>] lookup_positive_unlocked+0x1d 8 [<ffffffff950a6e2d>] debugfs_lookup+0x5d 9 [<ffffffff950a6e8f>] debugfs_lookup_and_remove+0xf 10 [<ffffffff94e60379>] debugfs_slab_release+0x19 11 [<ffffffff94dff59c>] kmem_cache_destroy+0x11c 12 [<ffffffffc0839625>] init_iso9660_fs+0x2615 13 [<ffffffffc083e039>] init_iso9660_fs+0x7029 14 [<ffffffff94bf6ea3>] __do_sys_delete_module.isra.0+0x1a3 15 [<ffffffff94bf7052>] __x64_sys_delete_module+0x12 16 [<ffffffff94a06330>] x64_sys_call+0x22f0 17 [<ffffffff95c1dc3f>] do_syscall_64+0x7f 18 [<ffffffff95e00130>] entry_SYSCALL_64_after_hwframe+0x78 done **** ``` 接下來要解決的是來不及釋放的 memory 初始化的時候會呼叫 `simplefs_init_inode_cache` -> `kmem_cache_create_usercopy` 可以分配一塊(simplefs_inode_cache 是一個 simplefs_inode_info) memory，為什麼不使用 kmallock 或是其他方法？ **記憶體 api** - kmem_cache_create_usercopy - kmem_cache_alloc - kmem_cache_destroy ext2 在 destroy 的 code 1. 我們有使用到 rcu call back fucntion 嗎 ? 在哪一段會使用到 ? 2. 順序也會影響問題，在 simplefs 中果先使用 `rcu_barrier` 會出現更多問題。 ```c static void destroy_inodecache(void) { /* * Make sure all delayed rcu free inodes are flushed before we * destroy cache. */ rcu_barrier(); kmem_cache_destroy(ext2_inode_cachep); } ``` 以下為 [`rcu_barrier`](https://www.kernel.org/doc/Documentation/RCU/rcubarrier.txt) 解釋以及 simplefs 改動 > Pseudo-code using rcu_barrier() is as follows: 1. Prevent any new RCU callbacks from being posted. 2. Execute rcu_barrier(). 3. Allow the module to be unloaded. ```c static void __exit simplefs_exit(void) { int ret = unregister_filesystem(&simplefs_file_system_type); if (ret) pr_err("Failed to unregister file system\n"); simplefs_destroy_inode_cache(); rcu_barrier(); pr_info("module unloaded\n"); } ``` @RoyHuang 問題 > 寫入檔案的時候(dd command), 也有 cache leak 的問題, tracing code 出現在 "block_wirte_begin/ generic_write_end" 這兩個裡面, 請教老師能否給個方向去解決 ## TODO: [issue #58](https://github.com/sysprog21/simplefs/issues/58) 當我們刪除一個 file 後，會發現 `ln -s` 失效並出現以下 error，這是 kernel 中的 ELOOP error。 ``` Too many levels of symbolic links ``` 為了找出問題，所以要先確定 `rm`, `ln -s` 做了什麼事，以下是 `vfs_symlink` 流程 ``` 3) | vfs_symlink() { 3) 0.304 us | from_vfsuid(); 3) 0.150 us | from_vfsgid(); 3) | from_kuid() { 3) 0.165 us | map_id_up(); 3) 0.443 us | } 3) | from_kgid() { 3) 0.150 us | map_id_up(); 3) 0.414 us | } 3) | inode_permission() { 3) 0.144 us | make_vfsuid(); 3) 0.145 us | make_vfsgid(); 3) | generic_permission() { 3) 0.151 us | make_vfsuid(); 3) 0.426 us | } 3) 0.146 us | security_inode_permission(); 3) 1.548 us | } 3) 0.145 us | security_inode_symlink(); 3) | simplefs_symlink [simplefs]() { 3) | simplefs_new_inode [simplefs]() { 3) | simplefs_iget [simplefs]() { 3) | iget_locked() { 3) 0.149 us | _raw_spin_lock(); 3) 0.580 us | find_inode_fast(); 3) 0.147 us | _raw_spin_unlock(); 3) | alloc_inode() { 3) | simplefs_alloc_inode [simplefs]() { ``` ## TODO: 整合 [jbd2](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html) 以具備 [journaling](https://en.wikipedia.org/wiki/Journaling_file_system) 特徵。 ### 為什麼要使用 journal [journal filesystem](https://en.wikipedia.org/wiki/Journaling_file_system) 透過記錄尚未提交到檔案系統主部分的變更來保持檔案系統的完整性。這些變更目標會被記錄在稱為 journal (這裡還不確定是 jbd2 的還是 filesystem 要自己定義)的資料結構中，這通常是一個環形日誌。當系統崩潰或電源故障時，這類 filesystem 可以更快地重新上線，並且降低 filesystem 損壞的可能性。 *journal mode* - writeback - order - journal **Rationale** 我們在這裡舉一個例子並搭配 [simplefs](https://github.com/sysprog21/simplefs) 的資料結構說明刪除一個 file 的流程 1. 移除 directory entry - 一個 file 的 parent 會以 `simplefs_file` 紀錄所有底下 file 或 directory 的資訊，所以必須刪除這項資訊。 2. 釋放 inode - 釋放對應 inode bitmap 3. 釋放 block - 釋放對應 block bitmap 探討一： 1->2 間發生 crash，會發生 storage leak，因為我們找不到對應的 inode 資訊，但其資料依然存在，且不可再被使用。探討二： 2->3 間發商 crash，inode 可以被釋放但是 block 依然不可使用所以想要維持一制性，就必須使用 [fsck](https://en.wikipedia.org/wiki/Fsck) 等工具來將整個 image 掃過一次，非常耗時。 **technique** journal 的形式有很多種設計，注意的是內部設計應該也要考慮寫日誌時發生的 crash。 - 動態 journal : 設計成普通 file 可以動態調整大小 - 固定 journal : 放在連續位置且 mount 後不會改變大小 - external journal : 放在獨立的 partition ***physical journals*** 將要寫入的 block 都預先複製成 journal，因此 recorvery 時只要將完整的 block 覆蓋或是丟掉未完成的 journal block，但這會造成效能瓶頸。 ***Logical journals*** 只記錄 metadata，這樣在速度以及效能上會有明顯的提升，相之而來的風險就是資料可能會是錯誤的，舉例來說 append 一個 file 時我們可以確保 metadata 是完整的但 append 的 block 並未寫入完成，可能會得到不正確的資料。 ### 觀摩這個版本的 [simplefs](https://github.com/psankar/simplefs/commits/master/) 有實作 journal，因此可以當作參考，取其精華，去其糟粕。選擇 inode 當作 journal 依據或是 new device 擇一，但是在這個版本卻都使用到了，可以在 `simplefs_parse_options` 選擇方式 - `simplefs_sb_load_journal` -> `jbd2_journal_init_inode` - `simplefs_load_journal` -> `jbd2_journal_init_dev` ### Journaling the Linux ext2fs Filesystem 設計原則 - 不會嚴重影響效能 - 不可影響相容性 - 不可影響可靠性 ### jb2 相關 function **jbd2_journal_start** @journal : Journal to start transaction on @nblcks : number of block buffer we might modify 開啟一個新的 handle **jbd2_journal_get_write_access** @handle: transaction to add buffer modifications to @bh: bh to be used for metadata writes 將 buffer head 加入 handle **jbd2_journal_dirty_metadata** @handle: transaction to add buffer to. @bh: buffer to mark 標記 bh 為已修改 **jbd2_journal_stop** @handle: transaction to complete. 完成一個 transaction **jbd2_journal_flush** 將 log flush 到原始位置 ### @Jason 設計概念先描述 journal 相關的 structure 以及在做 journal 時，相關 data block 的順序 - journal super block - first block in the journal - contains the first logging data address and its sequence number - Mark the oldest and newest non-checkpointed transactions inthe log in a journal superblock (用來知道那些舊的 journal 相關 log 可以刪除) - Journal descriptor block - Each transaction starts with a descriptor block - contains the transaction sequence number and a list of what blocks are being updated. - updated metadata block - commit block - 當我們把 `updated metadata block` 真正寫到 disk 的時候，會在 `commit block` 中記錄和 `descriptor block` 一樣的 sequence number，來表示完成這次 `journal` 的動作。我們知道完成一個 journal 主要會經過以下步驟 :point_right: 這邊先以 ext4 的 order mode 為例假如說我們今天有一個 file，他原本只有一個 data block ，但現在變成兩個，所以我們第一步會先去修改他的 inode 以及 block bitmap。 1. 先把 data 寫到 data block 2. 先將上述 metadata 的修改做 journal (這邊目前覺得要存 data、inode bitmaps 以及 inode) - 這邊在寫一個 transaction 的時候大概的 layout 會像這樣 - | TxB(transection beginning) | inode bitmap | data block bitmap | TxE(transaction ending) | | -------- | -------- | -------- | --| 3. Checkpointing ，把這些 transaction 裡面存的這些修改過的 metadata block 寫到 disk 的 final location 當中。 4. 在 journal superblock 裡面把這個 transaction 標記為 free 先參考[kernel document guide](https://elixir.bootlin.com/linux/v6.8/source/Documentation/filesystems/journalling.rst)使用 journal 的步驟 1. 先建立一個 `journal_t` 的資料結構，此資料結構最後會被 `jbd2_journal_destroy()` 使用，並釋放那些 kernel memory >jbd2_journal_destroy() - Release a journal_t structure. 2. 接著會因為 `journal` 儲存的地方不同，而會去呼叫不同的 linux kernel function - 如果是 internal 也就是 journal 放在同一個 partition，會在 mkfs 分配對應的 inode number，接下來在 mount 的時候會呼叫`jbd2_journal_init_inode()` - `journal` 存在 raw device(external journaling) 的話會呼叫 `jbd2_journal_init_dev()` :::info 但這邊覺得很奇怪，為什麼可以只呼叫上面幾個 jbd 的 api 就可以完成 journal 了，跟我想像中的要以 transaction 為單位來做事不同。 ::: 且裡面指出對於 journal 設計應先去參考 `ext4_load_journal()` 這個 function，而去 trace 的結果得到以下的 function flow :warning: 這邊的 function flow 目前是先看 v4.9.92 版本的 flow ，目前預計先參考較早期版本的 code 先將基本的 journal 功能建立 `ext4_fill_super` -> `ext4_load_and_init_journal` -> `ext4_load_journal()` -> `ext4_get_journal()`/`ext4_get_dev_journal()` `ext4_get_journal()` -> `ext4_get_journal_inode()` ->`jbd2_journal_init_inode()` -> `ext4_init_journal_params()` `ext4_get_dev_journal()` -> `ext4_blkdev_get()` -> `jbd2_journal_init_dev()` -> `ext4_init_journal_params()` 可以知道一開始在 `ext4_fill_super()`的時候，就要去把 journal 相關的 device 設定好，於是這邊也在 simplefs 中的 super.c 先實作出幾個 function :::warning 因為目前還是沒有 trace 到 ext4 他對於每次的 journal 放在 disk 中的 block layout 是怎麼樣，所以還無法在 mkfs 裡面劃分出 journal 的相關區域。 ::: ``` #### file.c 相關的修改 :::info 在 ext4 裡面的 `address_space_operation` 裡面會去區分用不同的 journal mode 而提供不同的 `address_space_operation` ::: 可以看到這邊在做 `iget()` 的時候，就會針對他這個 `inode` 對應到的是 `file` 的類型而去做對應的動作 ```c if (S_ISREG(inode->i_mode)) { inode->i_op = &ext4_file_inode_operations; inode->i_fop = &ext4_file_operations; ext4_set_aops(inode); ``` 然後裡面的 `ext4_set_aops()` 又會根據他的 journal 選擇的模式做出要去用哪一類型的 `address_space_operation`，但如果是 `order mode`、`write back mode` 就是使用 ext4 原先的 `address_space_operations ext4_aops` ```c void ext4_set_aops(struct inode *inode) { switch (ext4_inode_journal_mode(inode)) { case EXT4_INODE_ORDERED_DATA_MODE: case EXT4_INODE_WRITEBACK_DATA_MODE: break; case EXT4_INODE_JOURNAL_DATA_MODE: inode->i_mapping->a_ops = &ext4_journalled_aops; return; default: BUG(); } if (test_opt(inode->i_sb, DELALLOC)) inode->i_mapping->a_ops = &ext4_da_aops; else inode->i_mapping->a_ops = &ext4_aops; } ``` :::info 但我們這邊目前先將 `order mode` 做出來，所以並不需要提供這樣類似的 function ，如果之後要在提供 `data mode` 就是要在這邊下手。 ::: 然後這邊我們先來看一下在做 `write()` 的時候，會用到 journal ，所以我們就先來看一下 ext4 在做 write system call 的時候主要的 function flow `write()` -> `vfs_write()` -> `write_iter()` -> `ext4_file_write_iter()` -> `generic_file_write_iter()` -> `__generic_file_write_iter()` -> `generic_perform_write()` -> `ext4_write_begin()` -> `ext4_writepage()` -> `ext4_write_end()` :::info 而其中跟 journal 有關的操作則在 `ext4_write_begin()`、`ext4_write_end()` 裡面去完成，所以這邊對這兩個 function 去進行分析 ::: :::info 如何使用 external device ::: 1. 先到 simplefs 目錄中下 make journal ```bash insmod simplefs/simplefs.ko loop_device=$(losetup -f) losetup $loop_device /simplefs/journal.img mount -o loop,rw,owner,group,users,journal_path="$loop_device" -t simplefs /simplefs/test.img /test ``` :::info 如何在 qemu + gdb 的環境中開啟 jbd2 的 debug 以及 ftrace 功能 ::: 1. 先執行 make menuconfig > Kernel hacking > tracers > 然後把 `kernel function tracer`、`kernel function graph tracer` 打開 2. 開啟 `jbd2` debug 的相關設定，開啟完之後相關的 flag 會像下面得到 ` CONFIG_JBD2=y`、`CONFIG_JBD2_DEBUG=y` 3. 在 qemu 裡面做以下步驟 ``` bash echo 1 > /sys/module/jbd2/parameters/jbd2_debug dmesg | grep jbd2 mount | grep tracefs mount -t tracefs nodev /sys/kernel/tracing mount | grep tracefs echo function > /sys/kernel/tracing/current_tracer echo jbd2_* > /sys/kernel/tracing/set_ftrace_filter echo 1 > /sys/kernel/tracing/tracing_on cat /sys/kernel/tracing/trace #做自己要做的事情 echo 0 > /sys/kernel/tracing/tracing_on cat /sys/kernel/tracing/trace > ~/trace.txt ``` :::info 如何檢查 diskimg 以及 external journal device 資料是否被寫入 ::: 1. 先在 host 端 mount 剛剛在 qemu 上面掛載的 rootfs image `sudo mount rootfs.img /rootfs` 2. 進到 rootfs 內的 simplefs 目錄，應該會看到兩個 disk image 分別是 `test.img`(真正寫 data 的)、`journal.img` (journal external device) 3. 將 2 個 disk image 的內容轉成 .hex 然後輸出不為 0 的資料段，方便我們檢查。 ```bash xxd journal.img > disk.hex grep -v ' 0000 0000 0000 0000 0000 0000 0000 0000' disk.hex ``` :::danger dirctory 是「目錄」，不是「資料夾」，注意用語！ ::: :::info 以下實驗皆在 kernal v6.8 環境下並且以 qemu + gdb 方式進行 ::: 1. 先 insert simplefs kernal module ```bash Shrimp:/ # insmod simplefs/simplefs.ko [ 28.637195] simplefs: loading out-of-tree module taints kernel. [ 28.642219] simplefs: module loaded [ 28.643563] insmod (55) used greatest stack depth: 13448 bytes left ``` 2. 設定好 `external journal device` ，並在 mount simplefs filesystem 的時候透過 `fill_super` 一起掛載好。 ```bash Shrimp:/ # loop_device=$(losetup -f) Shrimp:/ # losetup $loop_device /simplefs/journal.img [ 39.321464] loop0: detected capacity change from 0 to 16384 Shrimp:/ # mount -o loop,rw,owner,group,users,journal_path="$loop_device" -t simplefs /simplefs/test.img /test [ 44.036081] loop1: detected capacity change from 0 to 409600 [ 44.042542] simplefs: simplefs_parse_options: parsing options 'owner,group,journal_path=/dev/loop0' [ 44.042986] simplefs: simplefs_get_dev_journal: getting journal for device 7:0 [ 44.043548] simplefs: simplefs_get_dev_journal: journal block device obtained, start=1, len=2048 [ 44.043835] simplefs: simplefs_get_dev_journal: journal initialized successfully [ 44.044288] simplefs: simplefs_fill_super: successfully loaded superblock [ 44.044463] simplefs: '/dev/loop1' mount success ``` 3. 新增兩個寫入測試檔案 ```bash Shrimp:/ # cd test/ Shrimp:/test # echo "ew[ 64.291460] random: crng init done Shrimp:/test # echo "test1" >test1.txt Shrimp:/test # echo "test2" >te[ 83.045112] JBD2: Spotted dirty metadata buffer (dev = loop1, blocknr = 921). There's a risk of f. Shrimp:/test # echo "test2 " > test2.txt ``` 4. 在 host 端中 mount `rootfs.img` 並檢查裡面內容 ```bash > sudo mount rootfs.img rootfs > xxd test.img > /home/shrimp/linux2024/workspace/qemu/linux-6.8/test.hex > xxd journal.img > /home/shrimp/linux2024/workspace/qemu/linux-6.8/journal.hex ``` 5. 分別檢視 disk image 內容 (截取部分重要內容) - journal.img (for journal data) ```bash 00000400: 0000 0000 0008 0000 0000 0000 0000 0000 ................ 00000410: 0000 0000 0000 0000 0200 0000 0200 0000 ................ 00000420: 0080 0000 0080 0000 0000 0000 0000 0000 ................ 00000430: 4050 7766 0000 ffff 53ef 0100 0100 0000 @Pwf....S....... 00000440: 4050 7766 0000 0000 0000 0000 0100 0000 @Pwf............ 00000450: 0000 0000 0b00 0000 0001 0000 0000 0000 ................ 00000460: 0800 0000 0000 0000 e7d5 c795 3d85 4bdd ............=.K. 00000470: a520 7d69 fd3d d1d3 0000 0000 0000 0000 . }i.=.......... 000004e0: 0000 0000 0000 0000 0000 0000 e229 e0e7 .............).. 000004f0: c4c8 4c9a a082 03bc 7135 2caf 0100 0000 ..L.....q5,..... 00000500: 0c00 0000 0000 0000 4050 7766 0000 0000 ........@Pwf.... 00000550: 0000 0000 0000 0000 0000 0000 2000 2000 ............ . . 00001000: c03b 3998 0000 0004 0000 0000 0000 1000 .;9............. 00001010: 0000 0800 0000 0002 0000 0002 0000 0002 ................ 00001030: e7d5 c795 3d85 4bdd a520 7d69 fd3d d1d3 ....=.K.. }i.=.. 00002000: c03b 3998 0000 0001 0000 0002 0000 0399 .;9............. 00002010: 0000 0008 0000 0000 0000 0000 0000 0000 ................ 00003000: 0000 0000 0000 0000 0800 0000 a203 0000 ................ 00004000: c03b 3998 0000 0002 0000 0002 0000 0000 .;9............. 00004030: 0000 0000 6677 50a8 3686 40b7 0000 0000 ....fwP.6.@..... 00005000: c03b 3998 0000 0001 0000 0003 0000 03aa .;9............. 00005010: 0000 0008 0000 0000 0000 0000 0000 0000 ................ 00006000: 0000 0000 0000 0000 0800 0000 ab03 0000 ................ 00007000: c03b 3998 0000 0002 0000 0003 0000 0000 .;9............. 00007030: 0000 0000 6677 50c2 000b b7f6 0000 0000 ....fwP......... ``` - test.img (writing real data) ```bash 00398000: 0200 0000 0000 0000 0800 0000 9a03 0000 ................ 00399000: 0000 0000 0000 0000 0800 0000 a203 0000 ................ 0039a000: 0200 0000 7465 7374 312e 7478 7400 0000 ....test1.txt... 0039a100: 0000 0000 0300 0000 7465 7374 322e 7478 ........test2.tx 0039a110: 7400 0000 0000 0000 0000 0000 0000 0000 t............... 003a2000: 7465 7374 310a 0000 0000 0000 0000 0000 test1........... 003aa000: 0000 0000 0000 0000 0800 0000 ab03 0000 ................ 003ab000: 7465 7374 3220 0a00 0000 0000 0000 0000 test2 .......... ``` 從上述實驗結果可以看到在 external journal device 中，`jbd2` 都會以 block 為單位來管理，每個 block 都會有一個都會以 12 bytes 的[`struct journal_header_s`](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html#block-header)作為起始。這邊先看到第一個 block 也就是 `journal super block (本文後面簡稱 jsb)` ```bash 00001000: c03b 3998 0000 0004 0000 0000 0000 1000 .;9............. 00001010: 0000 0800 0000 0002 0000 0002 0000 0002 ................ 00001030: e7d5 c795 3d85 4bdd a520 7d69 fd3d d1d3 ....=.K.. }i.=.. ``` 而參考文件 [`journal superblock struct layout`](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html#super-block) 我們可以得知 4 個 byte 是 `jbd2 的 magic number` ，接著 4 個 byte 會告訴我們是哪一類型的 block ，可以看到他的值為 `0004` 也就是 `Journal superblock, v2`。在來我們就要看另外一個比較重要的東西就是 `Compatible feature`、`Incompatible feature set` ，因為這兩個的值會關乎到後面 `descriptor block` 中的 disk layout。而這個 `jsb` 會在一開始透過 `make journal device` 的時候就會把它寫好，接著在 `fill_super()` 的時候會用 `load_journal` 來設定對應參數，並把 `jsb` 從對應位置讀上來並且檢查對應的 `magic number` 然後把 `journal` 的相關參數設定好。而從上面的結果可以發現 `Compatible feature` 對應的位置 `0x24` 的值為 0 ，也就代表說 `JBD2_FEATURE_INCOMPAT_CSUM_V3 is NOT set` ，所以 `descriptor block` 中的 [`descriptor blockdata layout`](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html#descriptor-block) 就會是`struct journal_header_s` + `struct journal_block_tag_s`(TODO:改圖示呈現) 然後我們每個 `transaction` 都會用一個 `descriptor block` 和`commit block` 包起來。接著第二個 block 就是我們的第一個 `transaction` 我們可以看到這邊的 `offeset 0x4： h_block type` 的地方 = 1 且 `offeset 0x8： h_sequence` = 2 ，代表說第一個 `transaction` 的 `log id` = 2 ，可以看到這個值跟 `jsb` 裡面 `offeset 0x14： s_first` （第一個 `transaction` 的 id) ，所以表示該 transaction 為整個 journal 的第一筆。 TODO:下面的內容有問題要在修改然後我們 descriptor block 裡面有設定的前面12 byte 一樣是 journal header 而後面的則是journal_block_tag_s 而這個tag裡面的內容要先去看 JBD2_FEATURE_INCOMPAT_CSUM_V3 這個 incompat 的 feature 是否有設成這個 flag ，會依照是否有設定而有不同的disk layout ### @HotMercury 設計概念預計會像是 [ext3](https://github.com/spotify/linux/tree/master/fs/ext3) 設計概念有一個 circular log 在 disk 中 *disk layout* ![image](https://hackmd.io/_uploads/SyU_pKEBR.png) 關於 transaction 這段，[文件](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html) 中有一段話，我的想法是這個 descriptor 應該要有所有 update 的對應位置資料，但在 kernel 中卻找不到相關的 array 來紀錄，可能跟 open code 有關系但我不太懂 open code 意義。 > The descriptor block contains an array of journal block tags that describe the final locations of the data blocks that follow in the journal. Descriptor blocks are open-coded instead of being completely described by a data structure, but here is the block structure anyway. Descriptor blocks consume at least 36 bytes, but use a full block: ![image](https://hackmd.io/_uploads/S1bVy5VB0.png) *descriptor 對應 data struct* ![image](https://hackmd.io/_uploads/rk5y1c4HA.png) **整體流程** 我們要實作的是 order mode 且要搭配 jbd2 api，先將 file data 的部份寫到對應的 fix 位置，接下來再將 metadata 寫入 log 位置，等確保 log 完成後可以做 check point 將資料從 log 寫入 fix，接著釋放。 **jbd2 api 及實作 function** 我們會使用到 `jbd2_journal_start` 建立一個新的 handle，此時會設定需要的 block 數量，這裡預計會實作 `simplefs_meta_trans_block` (這是模仿 ext3 `handle = ext3_journal_start(inode,EXT3_DATA_TRANS_BLOCKS(inode->i_sb));`)，接下來將 `jbd2_journal_get_write_access` 綁定對應的 bh，`jbd2_journal_dirty_metadata` 設為寫入狀態，`jbd2_journal_stop` 結束 transcation 接下來 `jbd2_journal_flush` 寫入 log 現在考慮一個議題 journal block 應該要放在哪裡？要有多大的空間？ `jbd2_journal_init_inode` 首先綁定對應的 inode，所以目前 mkfs 時會設定成以下狀態。 | 0 | 1 | 2 | | -------- | -------- | -------- | | empty | root | journal | ## 問題 - 新建立的 inode `simplefs_inode_info`，何時設定 i_mode, i_uid 等值? 應該說如果是 `simplefs_iget` 如果是 new inode，是不是等於多設定了多餘的動作 ``` simplefs_create() | \ | simplefs_new_inode() // 得到 inode number | | | simplefs_iget() // 去 cache 找沒有就 allocate 一個，但是這裡會有多餘的設定 | / 正確的 inode 設定 ``` > simplefs_iget ```c inode->i_mode = le32_to_cpu(cinode->i_mode); i_uid_write(inode, le32_to_cpu(cinode->i_uid)); i_gid_write(inode, le32_to_cpu(cinode->i_gid)); inode->i_size = le32_to_cpu(cinode->i_size); ``` - 在 [psankar/simplefs](https://github.com/psankar/simplefs) 裡面，mkfs 會呼叫 `write_journal_inode` 和 `write_journal`來對 patition 進行 journal 相關的初始化動作，但在 `ext4` 中，如果是用 `internal ` 的 journal ，會是怎麼樣去把 journal 相關的區域先劃分出來，然後整個 disk 的 layout 又是長什麼樣子? 因為目前在 [Ext4 document](https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Layout) 中，僅有看到以下的示意圖 ![ext4-doc](https://hackmd.io/_uploads/SycTsOtmR.png) - 而且在他的 code 中可以看到，無論是用 internal/external 的 device，他的 mkfs 都會是一樣的方式，但這樣的行為我覺得很奇怪，為什麼今天如果是用 external device 去存 journal 的話我們還要在原本的 disk image 去規劃區域給他? - 如何知道斷電後哪些 transaction 是沒有真的寫到 disk fix location 中的: :::info 如果記在 `journal super block` 裡面不可行，因為如果記在 super block 裡面代表說每次在 journal 寫到 fix location 的時候，也需要把這個 `journal super block` 一起更新 ::: ## 參考資料 - [The Linux Journalling API](https://docs.kernel.org/filesystems/journalling.html) - [Journal (jbd2)](https://www.kernel.org/doc/html/latest/filesystems/ext4/journal.html) - [On-disk Journal Data Structures (JBD2) ](https://blogs.oracle.com/linux/post/ondisk-journal-data-structures-jbd2) - [File Systems – Journaling](http://nyx.skku.ac.kr/wp-content/uploads/2019/11/13-Journaling.pdf) - [Journaling the Linux ext2fs Filesystem](https://pages.cs.wisc.edu/~bart/736/papers/ext3-journal-design.pdf)

Read more

2024 年 Linux 核心設計/實作課程期末專題

2024 年 Linux 核心設計/實作課程期末專題

從 √2 的存在談開平方根的快速運算

Linux 核心專題: 排程器研究