# 2024q1 Homework5 (assessment)
contributed by < `eleanorLYJ` >

:::danger
依據指定格式書寫
:::

## 記錄閱讀〈因為自動飲料機而延畢的那一年〉的啟發
從這段文字中，我感受到了作者在實踐一個看似瘋狂又充滿挑戰的冒險。他的故事從一種幽默的角度開始，而過程中是對技術和決策的深刻思考。作者不斷地面臨各種挑戰，其中一個挑戰是筆者要自幹冰塊分配器，然而他怎麼嘗試怎麼失敗，隔著螢幕都感受到絕望，讓我想替他放棄，然而但就像 jserv 說: 「**該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大**」的一樣，我得理解冷靜處理和承受失敗的重要性。

這段故事讓我深刻理解到系統軟體開發的態度。從作者的經歷中，我看到了解為甚麼要對細節的極度重視，因為踏出軟體世界，胡亂試錯的成本極高的情況下，冷靜的分析和實驗成為解決問題的關鍵，如同筆者寫的 : 「**解決問題的唯一方法就是冷靜下來分析，做實驗把變因排除掉。**」期望自己面對問題我也能冷靜下來。另外的啟發是，倘若我卡在某個一定有人解決過的問題，比起孤軍奮戰，更該開口詢問他人或是觀摩他人的作法，就如同本門課作業要我們從觀摩其他學員的成果相同，借鏡他人經驗吸取教訓，最後重新投入到自己的作品中，這樣的反思與學習態度是重要的。

## 課程的心得和提問
### 問題1.
我在 [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec) 文章看到，fork 在linux 核心資料結構的開銷，就是 fork 會複製親代行程的分頁表與 vm_area_struct ，然後不清楚 vm_area_struct的具體功能，

我的疑問是，是否有操作會同時使用到分頁表和 vm_area_struct 這兩個資料結構？分頁表處理的是實體地址與虛擬地址的映射，而 vm_area_struct 則維護程序申請的每一塊記憶體空間，其中包括虛擬地址的起始地址和 page-fault handlers 等。因此，如果要執行該程序，是否根據 vm_area_struct 的資訊來查找對應的分頁表，然後再將其加載進主記憶體？

#### sol: 看fork() 如何做 CoW 的操作：
fork()後，親代行程的虛擬地址空間（包括分頁表和 vm_area_struct）會被複製到子進程。memory page 被設置為只讀，行程共享。共享的進程的分頁表條目都指向相同的 physical page，但設置為只讀。當如果嘗試寫入 Cow 頁時，系統會分配一個新的physical page，將原頁的內容複製到新頁，並更新行程的分頁表，使其指向新頁，並設置為可寫。

### 問題 2.
同樣文章: [UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)
> 我們知道使用者層級行程申請的每塊記憶體空間，在系統核心中均以 vm_area_struct 所維護。如果我呼叫 10000 次 mmap，那就有 10000 個 vm_area_struct 物件被建立。在 fork 呼叫中，即使沒有任何對記憶體寫入的操作，這 10000 個 vm_area_struct 依然會被複製。因此在這個例子中，一次 fork 呼叫的記憶體消耗至少是 10000 * sizeof(struct vm_area_struct)
這往往沒必要，因為子行程一般都會呼叫 exec，從而釋放掉這些地址空間的記憶體以及對應的 vm_area_struct 物件。

1. "子行程一般都會呼叫 exec"這句話中為甚麼不是exec 而是 exit? 還是這段是指 exec 會釋放掉當前的 process image 而改替代程子行程的
2. 如果一個行程做了mmap 1000次, 子行程的 vm_area_struct 會與親代行程長得不一樣?

<!--
jserv答:
- exec 僅是 replace
- cachline常見是64bits -->
### 問題 3.
在[Memory Barriers Are Like Source Control Operations](https://preshing.com/20120710/memory-barriers-are-like-source-control-operations/)文章中的譬喻
> Which brings us to the source control strategy. In this analogy, the source control strategy is very strange indeed. As Larry and Sergey modify their working copies of the repository, **their modifications are constantly leaking in the background**, to and from the central repository, at totally random times. Once Larry edits the file X, his change will leak to the central repository, but there’s no guarantee about when it will happen. It might happen immediately, or it might happen much, much later. He might go on to edit other files, say Y and Z, and those modifications might leak into the respository before X gets leaked. In this manner, stores are effectively reordered on their way to the repository.

不是很清楚他譬喻的意思，
這兩個使用者不定時操作，並且他們在各自 copies 的 repo 中的修改，其修改會不斷的在背景洩漏。
1. in the background 的意思是說不讓另一個使用者知道修改，而已向主要的倉儲送修改?
2. 然後造成類似ABA問題?

<!-- jserv回答並非ABA問題，ABA問題是指 atomic operation只能保護一個整數的操作，其餘於資料結構並能保證到他的順序不會被改動，而以上敘述並未涉及到ABA問題。 -->

### 問題 4.
文章[透過 Model Checking 學習並行處理](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-model-checking)中，Dekker's Algorithm 的程式碼是用什麼方式轉化成那樹狀結構?
### 四個 memory barrier
我的粗淺理解
- LoadLoad 確保此 barrier 之前的 load 操作不會與 barrier 之後的 load 操作 有相對順序的改變。
- StoreStore 確保此 barrier 之前的 store 操作不會與 barrier 之後的 store 操作 有相對順序的改變。
- LoadStore 這是一個不貴的操作。只保證了周圍的操作不會被重排序。 並且如果 發現 load 與 前後出現的 store 無關，可以先跳過 load，稍後再處理。
- StoreLoad 確保所有的 load 操作都在 barrier 之後操作。

### lock-free linkedlist 的 delete()
目前沒有做 Garbage collection。
目前 search() 若有看到 mark 的節點，那就被用 CAS 移出串列中，並外釋放記憶體。
因此我在想在 struct list 中，多加一個 `node *garbage_list` 的成員，因此在 remove 中除了做 mark 以外，也將 mark的節點的指標複製接到 garbage_list 中，在 search 中把 garbage list 中刪除。
> 待檢驗

## 自訂專題題目
1. 探討 某 lock-free 案例
2. Linux 核心採納 Rust
### 3. 理解 當前 linux 中如何做測試
#### 專題動機
因為看到邱冠維同學在 open source summit 發表的投影片裡的最後一頁談論到 "The library code also lacks comprehensive testing"，因此我好奇當前 linux 中測試的現況與有何改進空間。
#### 期末專題架構
跟隨[Kernel Testing Guide](https://docs.kernel.org/dev-tools/testing-overview.html) 的大綱順序:

撰寫並執行測試
- **KUnit**: an entirely in-kernel system
for "white box" testing
- kselftest is largely implemented in userspace, and tests are normal userspace scripts or
programs.

程式覆蓋率檢查工具
- `Documentation/dev-tools/gcov.rst`
- `Documentation/dev-tools/kcov.rst`

動態分析工具
- **kmemleak** detects possible memory leaks.
- **KASAN** detects invalid memory accesses such as out-of-bounds and use-after-free errors.
- **UBSAN** detects behaviour that is undefined by the C standard, like integer overflows.

靜態分析工具
- **Sparse** can help test the kernel by performing type-checking, lock checking, value range checking, in addition to reporting various errors and warnings while examining the code.
- **Smatch** extends Sparse and provides additional checks for programming logic mistakes such as missing breaks in switch statements, unused return values on error checking, forgetting to set an error code in the return of an error path, etc.

最後看當前 `inux/lib/test_sort.c` 的程式

---

[ctp: C Thread Primitives](https://github.com/nicowilliams/ctp)

TODO: 提問
TODO: 看 ctp

筆記: [期末專題: 閱讀 ctp](/uTHTA1zvSQWzawvj4uHGeg)