# W4 Personal Reflection

## 提交第一份 Patch 1
[第一次給Linux Kernel發patch](https://hackmd.io/@rhythm/BkjJeugOv)

> 維護者與維護者的溝通，還有Linus與維護者們的溝通大多不會Cc LKML，他們的工作方式我還沒有深入去查過。
>
Linux kernel開發社群討論使用 mailing list，使用 broadcast 方式溝通, 叫做 Linux Kernel Mailing List (LKML)

> 第一行是子系統名稱以及patch標題，應盡量精簡到位，讓維護者一下就知道你做了什麼
第二部分是patch的內容，時態用現在式，語態用主動形式
第三部分是使用-s生成的簽名
中間要有空行

git commit 除了字數以及內容的 7 限制原則, 也加入上方的修正原則

> 接著生成patch:
$ git format-patch master

> 用 script 檢查 patch 有沒有問題:
$ ./scripts/checkpatch.pl 0001-Documentation-x86-fix-a-missing-word-in-x86_64-mm.rs.patch

> 用 script 查看這個 patch 要給誰:
$ ./scripts/get_maintainer.pl -f Documentation/x86/x86_64/mm.rst

> 現在的 linux kernel 是用 sphinx 來把.rst變成html，所以理論上改Documentation, **除了用 script 檢查 patch, **也應該**用 sphinx 測試過一次**

現在的 linux kernel 是用 sphinx 來把.rst變成html，所以理論上改Documentation, **除了用 script 檢查 patch, **也應該**用 sphinx 測試過一次**

> 我一開始拿來改的tree似乎是錯誤的，我要改Documentation的話感覺應該是要使用Jonathan Corbet在lwn.net上的git tree來改才對
這個Documentation的patch真的是超級新手友善，因為不是跑code所以很多的測試都省掉了，改code官方建議是要找四五台電腦compile跑看看確認沒問題再提patch

要確定要修改的 Documentation 的 git tree 是哪個.

> 我沒有注意到merge window的問題，但運氣太好了剛好就在v5.10的其中發出去，不知道如果沒有在merge window中發patch會怎樣
>
提交修改 patch, 要在 merge windwos 之內.

`./scripts/checkpatch.pl 0001-Documentation-x86-fix-a-missing-word-in-x86_64-mm.rs.patch
total: 0 errors, 0 warnings, 8 lines checked
`
`$ ./scripts/get_maintainer.pl -f Documentation/x86/x86_64/mm.rst`

最後要紀錄後記與一些疑問, 避免再次出錯

### What is Merge window?
[Merge_window](https://en.wikipedia.org/wiki/Merge_window)

合併視窗是一個**軟體開發過程**，有時被大型專案使用。
合併視窗是在軟體的**新版本發佈後** 的一段時間。在此期間，許多補丁被合併，因此在下一個版本之前有很長的時間進行審查和測試。
自 2005 年 7 月發布 2.6.14 版本以來，Linux 內核一直使用合併窗口進程。從那時起，每個 2.6.*、3.* 和 4.* 版本之後都會有一個**為期兩周的合併視窗**。

所以要提交修改 patch, 要在 merge windwos 之內.

:::info
疑問: sphinx 是什麼?
疑問: 要怎麼確定 git tree 是哪個?
疑問: 什麼時候有 merge windows?
:::

## 提交第一份 Patch 2
[提交第一份 Patch 到 Linux Kernel](https://hackmd.io/@steven1lung/submitting-patches)

“Only wimps use tape backup. REAL men just upload their important stuff on ftp and let the rest of the world mirror it.” –Linus Torvalds

> 在看老師的書 Demystifying the Linux CPU Scheduler 的時候，突然好奇說每一個任務的 loading 是如何運算的，畢竟排程器上的任務如此多，計算出 load 然後依據每個 CPU 的狀態去做 task migration 應該是很重要的課題。所以我就跑去 pelt.c 看了一下實際的運算是如何做到的。
pelt 全名是 Per Entity Load Tracking

如何找提交的 patch 目標?
學長經驗:
1. 鎖定有興趣的主題, 或 **沒有交待清楚** 的主題 (學長選擇 CPU 排程中, loading 計算方式)
2. 去看這個主題的負責程式 (學長選擇 pelt.c )
3. 找到文字或程式可優化部份
4. 照學長姐經驗送出 patch

> 寄送 Patch
> 找出 maintainer 是誰，並且將 patch 寄給他，這邊舉修改 docs 為例：
> $ ./scripts/get_maintainer.pl ./patch_name.patch

> 從輸出就可以看到要寄給的人了，通常裡面的人都會要 CC 到。
> $ git send-email --to [e-mail] \
--cc [e-mail] \
--cc [e-mail] \
./patch_name.patch

使用 get_maintainer 之後記得用 `send-email` 把 patch 送出.

> 使用 mutt：
$ mutt -H ./patch_name.patch

> 送出之後就可以到 lkml.org 看看有沒有出現你的 patch 了，靜靜等待 review 就好了。

:::info
疑問: mutt 是什麼?
:::

## 提交第一份 Patch 3
[第一次發 patch 到 LKML](https://hackmd.io/@Risheng/ry5futJF9)

> 這次發 patch 的機會主要是在修 jserv 老師的 Linux 核心實作課程，寫 quiz3 的作業時，我有對第一題的巨集 GENMASK 做一些的分析，也從老師得知在 kernel 裡其實有很多同名且功能相似甚至相同的函式或巨集，因此老師鼓勵我可以試著發送 patch 看看，我就想說來既然機會來了就嘗試看看，也就有了這次的提交，提交紀錄在這裡

如何找提交的 patch 目標?
學長姐經驗:
1. 寫作業時，對某些題目做過分析, 跟老師討論 (學長選擇巨集 GENMASK )
2. 去看這個主題的負責程式 (學長選擇 pelt.c )
3. 找到文字或程式可優化部份
4. 照學長姐經驗送出 patch

> git 有提供一個命令 git send-email 來做到發出信件的功能，或是也有很多人會使用 mutt 來幫忙發 plain text mail。我自己是 send patches 時會使用 git send-email，如果只是回覆 comment 之類就會用 mutt

- **git send-email** 來做到 **send patches**
- **mutt** 來幫忙發 plain text mail = **回覆 comment**

> 安裝 git send-email
參考 [How to configure and use git send-email with gmail](https://stackoverflow.com/questions/68238912/how-to-configure-and-use-git-send-email-to-work-with-gmail-to-email-patches-to)

要使用命令安裝 git send-email
並透過輸入命令 vi ~/.gitconfig ，在最後加上資料來設定 smtp 的資料，

>[sendemail]
smtpencryption=tls
smtpserver=smtp.gmail.com
smtpuser=<你的信箱@xxxx.com>
smtpserverport=587
smtpPass=<你的APP密碼>

## 提交第一份 Patch 4

>會想要提交這個 commit 主要是因為上班的時候看到 i2c 沒有處理 endian 調換的問題。但是因為沒有這方面的經驗，又看到一個 API 有多餘的判斷式，才想說拿這個比較有把握可以被接受的試試看。
>結果 patch 出去之後等了三個禮拜沒有回應，當我想寄第二封信的時候，就收到 reviewer 的回應了，reviewer 一開始就看到簽名的問題就有提醒我，改完簽名就收到 accept 啦

如何找提交的 patch 目標?
學長姐經驗:
1. 寫程式, 看到正在處理得部份, 有自己知道的問題 (學長寫 i2c 發現沒有處理 endian 調換 )
2. 照學長姐經驗送出 patch

:::info
疑問: linux 什麼程式會用到 i2c?
:::

## 實際操作

Step 1: 安裝 `git send-email`
使用 sudo apt install git-email 安裝, 會自動安裝 additional package, 花一點時間

Step 2: 輸入 git send-email 的 smtp 設定
使用 vim 設定 ~/.gitconfig, 用指令 :$ 跳到最後一行, 複製貼上

Step 3: git clone https://github.com/torvalds/linux.git
要等一段時間

## [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)

> red-black tree (以下簡稱 rbtree 或紅黑樹) 是一種特別的自平衡樹，不僅其新增、移除、搜尋的時間複雜度均維持在 $O(\log{n})$

> VMA（Virtual Memory Area）也用紅黑樹來紀錄追蹤頁面 (page) 變更，因為後者不免存在頻繁的讀取 VMA 結構，如 page fault 和 mmap 等操作，且當大量的已映射 (mapped) 區域時存在時，若要尋找某個特定的虛擬記憶體地址，鏈結串列 (linked list) 的走訪成本過高，因此需要一種資料結構以提供更有效率的尋找，於是紅黑樹就可勝任。

鏈結串列 (linked list) 為什麼走訪成本過高? => 走訪要經過O(n) 遠大於 O(lg n)

> 在樹高性質上，[AVL tree](https://en.wikipedia.org/wiki/AVL_tree) 和 rbtree 雖然都是 $O(\log n)$ ，但 AVL 在樹高上較緊致，約 $1.44 \times \log(n+2)$，而 rbtree 則為 $2 \times \log(n+1)$。因此在搜尋等以樹高作為上限的操作下， AVL tree 會比 rbtree 略快，但這是建立在新增和移除需要更多旋轉 (rotate) 以維持樹高的情形（其中 AVL tree 為 3 次，rbtree 為 2 次）。也因此，對於一般實作，Linux 核心偏好採用 rbtree (但近年轉向本文後續探討的 "maple tree")，資料庫的實作會傾向採用 AVL tree。

提出比較如同 "在樹高性質上.... AVL tree 和 rbtree 比誰計算樹高快" 時, 要提出各自在相同條件下的數學式, 就可以直接在理論上了解差異
但是優勢伴隨的前提條件需要提出來比較, 例如 AVL tree 強化樹高平均時, 會在**新增和移除**增加了更多旋轉 (rotate)的操作,

> 說明不同資料結構適用場景：當輸入的 indexes 特性為之間的變化極大又偏向一邊，亦即每個 index 之間的差距都頗大的情況，應採用 radix tree，後者本質上是稀疏陣列，有用到的 indexes 才會建立其空間陣列，這也是為何核心文件強調 "must be tuned for a specific size"。在此情況中，若使用 rbtree 將遭遇大量旋轉，因為當資料都偏向一方時，rbtree 本身又是一個自平衡樹，為維護平衡就只能頻繁的旋轉，如此一來，時間開銷就相當可觀。然而，當採用的資料 indexes 浮動不大，rbtree 會是很好的選擇，因為無需事先配置陣列或記憶體

:::info
specific size 有多大？ [核心文件](https://docs.kernel.org/core-api/rbtree.html)參考的是那一個文件或論文？
:::

> Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and file systems.
>
B 樹是一種自平衡樹數據結構，它維護**排序**數據並允許在對數時間內進行搜索、順序訪問、插入和刪除。**B 樹概括了二叉搜索樹**，允許具有兩個以上子節點的節點。 [2] 與其他自平衡二叉搜索樹不同，B 樹非常適合**讀取和寫入**相對**較大**的數據塊的**存儲系統**，例如資料庫和文件系統。
目的是有效地管理大型隨機存取檔**的索引頁**。基本假設是索引會非常龐大，以至於只有樹的一小部分可以容納在主記憶體中。Bayer 和 McCreight 的論文 Organization and maintenance of large ordered indices [1] 於 1970 年 7 月首次發行，後來發表在 Acta Informatica 上