# 2025q1 Homework1 (ideas)

contributed by < `willy-liu` >

[2024 年 Linux 核心設計/實作課程期末展示](https://hackmd.io/@sysprog/linux2024-showcase)

[2024 年 Linux 核心設計/實作課程期末專題](https://hackmd.io/@sysprog/linux2024-projects)

## [simplefs](https://hackmd.io/@sysprog/r1e08fg7A)

目標是為了教學的一個簡易版、直觀的檔案系統。
### 目前不懂的
不懂的詞彙：
- 不同的檔案格式
- ext4, btrfs
- IOPS(simpleFS的IOPS很好主要是因為操作太有限?)
- Issued rwts
- Partition layout
- superblock
- inode store
- bitmap(記錄哪裡還有空間)
- inode bitmap
- block bitmap
- data block
- extent block
- raw data
- `ftrace`, `fio`指令
- `generic_file_read_iter`
- `direct entry`
- journal
:::spoiler `Partition layout` grok的解釋
檔案系統的 Partition Layout（分區布局），這是檔案系統在儲存裝置（如硬碟或 SSD）上組織資料的方式。不同的檔案系統（例如 ext4、XFS、Btrfs）有不同的布局細節，但你列出的這些元素——superblock、inode store、bitmap（包括 inode bitmap 和 block bitmap）、data block（包括 extent block 和 raw data）——是許多現代檔案系統（如 ext 系列）共有的基本組成部分。我會逐一解釋這些概念，並說明它們在分區布局中的角色。

Partition Layout（分區布局）
分區布局指的是檔案系統如何將儲存空間分成不同的區域，用來存放元資料（metadata）和實際資料（data）。這些區域通常是連續或分散的區塊（blocks），每個區塊有固定大小（例如 4KB）。以下是各部分的解釋：

1. Superblock（超級塊）
* 定義：Superblock 是檔案系統的「控制中心」，存放檔案系統的全局元資料。
* 內容：
* 檔案系統的總大小（總塊數）。
* 塊大小（block size，例如 4KB）。
* 可用空間和已用空間的統計。
* 指向其他關鍵結構（如 inode store 或 bitmap）的指標。
* 檔案系統的類型（如 ext4）和狀態（如乾淨或損壞）。
* 位置：通常位於分區的開頭（例如第 0 或第 1 塊），並可能有多個備份副本分散在分區中，以防損壞。
* 作用：作業系統在掛載（mount）檔案系統時，首先讀取 superblock，了解檔案系統的結構和狀態。
* 例子：在 ext4 中，superblock 包含檔案系統的 UUID 和最後掛載時間。

---

2. Inode Store（inode 儲存區）
* 定義：Inode（索引節點）是一個資料結構，用來描述檔案或目錄的元資料。Inode Store 是存放所有 inode 的區域。
* 內容：
* 檔案權限（讀、寫、執行）。
* 擁有者（UID/GID）。
* 檔案大小。
* 時間戳（創建、修改、訪問時間）。
* 指向資料塊（data block）的指標（可能是直接指標或間接指標）。
* 位置：通常緊跟在 superblock 之後，或者分散在分區的多個「塊組」（block group）中。
* 作用：每個檔案或目錄對應一個 inode，inode store 就像檔案系統的「電話簿」，記錄每個檔案的元資料和資料位置。
* 例子：在 ext4 中，每個 inode 固定大小（例如 256 位元組），數量由格式化時決定。

---

3. Bitmap（位元圖，記錄哪裡還有空間）
* 定義：Bitmap 是一個位元陣列（bit array），用來追蹤分區中哪些資源（inode 或資料塊）已被使用，哪些是空閒的。
* 子類型：
* Inode Bitmap（inode 位元圖）：
* 用來記錄 inode store 中哪些 inode 已分配，哪些是空閒的。
* 每個位元（bit）對應一個 inode，0 表示空閒，1 表示已使用。
* Block Bitmap（塊位元圖）：
* 用來記錄資料塊（data block）中哪些塊已分配，哪些是空閒的。
* 同樣，每個位元對應一個資料塊。
* 位置：通常與 superblock 和 inode store 放在一起，可能按塊組（block group）組織。
* 作用：當創建新檔案或寫入資料時，檔案系統查詢 bitmap，找到空閒的 inode 或資料塊。
* 例子：假設有 8 個塊，block bitmap 是 11001000，表示第 1、2、5 塊已使用，其餘空閒。

---

4. Data Block（資料塊）
* 定義：Data Block 是存放實際檔案內容（而不是元資料）的區域。
* 子類型：
* Extent Block（範圍塊）：
* 定義：用來記錄連續資料塊的範圍（extent），而不是單個塊的指標。
* 結構：通常包含起始塊號和長度（例如「從塊 1000 開始，連續 10 塊」）。
* 優點：比傳統的直接/間接指標更高效，特別適合大檔案，因為它減少了指標數量。
* 例子：ext4 使用 extent tree（範圍樹）來管理大檔案的資料塊。
* Raw Data（原始資料）：
* 定義：檔案的實際內容（例如文字、圖片、影片資料）。
* 位置：存放在由 inode 或 extent block 指向的資料塊中。
* 例子：如果你寫入一個 "Hello World" 的文字檔案，這些字元就儲存在 raw data 區域。
* 位置：通常佔據分區的大部分空間，位於元資料區域（superblock、inode store、bitmap）之後。
* 作用：儲存使用者資料，是檔案系統的最終目的。

---

整體布局範例（以 ext4 為例）
在 ext4 這樣的檔案系統中，分區被分成多個 Block Group（塊組），每個塊組包含：

1. Superblock（超級塊）
- 數量：通常只有第一個塊組（Block Group 0）有主 superblock，但 ext4 會在分區中分散多個備份（例如 Block Group 1、3、5 等，具體取決於分區大小和格式化選項）。
- 位置：在 Block Group 0 的開頭（偏移量 1024 位元組，前面留空給啟動程式）。
- 為什麼有備份？：如果主 superblock 損壞，系統可以用備份恢復檔案系統。
5. Inode Store（Inode Table，inode 儲存區）
- 數量：每個塊組都有自己的 inode table。
- 內容：存放該塊組內所有檔案和目錄的 inode（每個 inode 固定大小，例如 256 位元組）。
- 大小：在格式化時決定整個分區的 inode 數量，然後平均分配到各塊組。
9. Inode Bitmap（inode 位元圖）
- 數量：每個塊組有一個。
- 大小：通常只佔一個塊（例如 4KB），能記錄該塊組內所有 inode 的使用情況（每個位元對應一個 inode）。
- 作用：標記哪些 inode 已分配，哪些是空閒的。
13. Block Bitmap（塊位元圖）
- 數量：每個塊組有一個。
- 大小：也通常是一個塊，能記錄該塊組內所有資料塊的使用情況。
- 作用：標記哪些資料塊已使用，哪些是空閒的。
17. Data Blocks（資料塊）
- 數量：每個塊組的大部分空間都用來存放 data blocks。
- 內容：包括檔案的實際資料（raw data）和可能的 extent block（用來管理大檔案的連續塊）。
- 大小：取決於塊組的大小和元資料佔用的空間，通常是塊組中最多的部分。

---

範例：1GB 分區的布局
假設：

分區大小：1GB（1024MB）。
塊大小：4KB。
塊組大小：128MB。
總塊組數：1024MB ÷ 128MB = 8 個塊組。
每個塊組約有 32,768 塊（128MB ÷ 4KB），結構可能如下：

* Block Group 0：
* 主 Superblock (1 塊)
* Group Descriptor Table (幾塊)
* Inode Bitmap (1 塊)
* Block Bitmap (1 塊)
* Inode Table (例如 64 塊)
* Data Blocks (剩餘約 32,700 塊)
* Block Group 1：
* 備份 Superblock (1 塊)
* Group Descriptor (幾塊)
* Inode Bitmap (1 塊)
* Block Bitmap (1 塊)
* Inode Table (64 塊)
* Data Blocks (剩餘)
* Block Group 2-7：
* 無 Superblock（或某些有備份）
* Group Descriptor (幾塊)
* Inode Bitmap (1 塊)
* Block Bitmap (1 塊)
* Inode Table (64 塊)
* Data Blocks (剩餘)

---
這些部分的關係
* Superblock 提供全局資訊，告訴系統去哪找 inode 和資料。
* Inode Store 記錄每個檔案的元資料，並指向 Data Block。
* Bitmap 管理資源分配，確保檔案系統知道哪裡有空位。
* Data Block 儲存實際內容，Extent Block 優化大檔案的存取效率。
* 總結

---

* Superblock：檔案系統的總覽和元資料。
* Inode Store：檔案的元資料儲存區。
* Bitmap：資源分配的記錄簿（inode bitmap 和 block bitmap）。
* Data Block：實際資料的家（extent block 管理大檔案，raw data 是檔案內容）。

:::


### 貢獻 - 讓simplefs 支援 linux v6.8

- no previous prototype...
由於新版的GNU/Linux在makefile中會強迫檢查`missing-prototypes`，所以必須先加上prototype define或是在函式內加上static。
要注意的是如果將函式宣告成static的話，作用域只會在該.c檔，所以只有helper function或是只在該檔案內部使用的函式才能被宣告成static。

- no member nameed i_atime
他們利用git blame來輔助查看錯誤訊息的部分下了什麼commit msg以及對應的理由是什麼。然後發現從`v6.7-rc1`某次commit為了讓使用者無法直接存取，而將它重命名了。

- implict declaration of function 'block_write_full_page'
和i_atime一樣，從`v6.8-rc1`

### 貢獻 - 修正 [Issue #20](https://github.com/sysprog21/simplefs/issues/20)

### 測試將一些無意義的值寫入image

他們分別測試了兩個指令
`dd if=/dev/zero of=test.img bs=1M count=200`
`dd if=/dev/random of=test.img bs=1M count=200`

他們發現如果將`0`寫入`test.img`的話是正常的；
但是將隨機數寫入的話就會發生錯誤。

原因在於`extent block`沒有在初始化時清空資料，導致指到`raw block`就亂指。(metadata沒有正確清空內部結構)

### 實作 File operations
他們透過使用`ftrace`, `fio` 追蹤file operation 會發生什麼事情，實作了以下的函式

- simplefs_read
- simplefs_open
- simplefs_write

值得注意的是他們不經過page cache，直接操作disk的空間，也沒有使用`generic_file_read_iter`等函式。

### 實作 改善Remove file的操作

原本的做法會使用後面的檔案全部往前位移的方式去覆蓋刪除的那個區塊，雖然可以保持空間的`direct entry`緊密性關係，然而代價會耗費大量的性能，他們改為將空間mark為non-use的方式實作

### 整合 jbd2 以具備 journaling 特徵

Journal: 讓資料保持一致性

## [全向量視窗系統實作](https://hackmd.io/@sysprog/B13GqdgQ0)

## [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)
[](https://hackmd.io/@charliechiu/linux2025-ideas)

## [針對鏈結串列的資料排序改進](https://hackmd.io/@sysprog/BJPBcQ34C)

## [CPU 排程器](https://hackmd.io/@sysprog/BJdyxvxX0)

## [排程器研究(yenslife)](https://hackmd.io/@sysprog/rysYj43ER)

## [亂數產生器研究](https://hackmd.io/@sysprog/BkhlALt8A)

## ~~[建構 RISC-V 相容處理器並運作 Linux 核心](https://hackmd.io/@sysprog/HyjiP43N0)~~