# 第一次嘗試貢獻 Linux 核心

contributed by <`yanjiew1`>

## 我打算做的貢獻

就在閱讀 `list_sort.c` 的原始碼過程中，發現 `list_sort.c` 內的 `merge` ，搭配[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)的技巧，透過 indirect pointer 的方式減少 if 敘述，故很快的就就做了相關的修改，如下：

diff --git a/lib/list_sort.c b/lib/list_sort.c
index 0fb59e92ca2d..9d12e50088ab 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))
 static struct list_head *merge(void *priv, list_cmp_func_t cmp,
 				struct list_head *a, struct list_head *b)
 {
-	struct list_head *head, **tail = &head;
+	struct list_head *head, **tail = &head, **node;
 
-	for (;;) {
+	for (node = NULL; a && b; *node = (*node)->next) {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			*tail = a;
-			tail = &a->next;
-			a = a->next;
-			if (!a) {
-				*tail = b;
-				break;
-			}
-		} else {
-			*tail = b;
-			tail = &b->next;
-			b = b->next;
-			if (!b) {
-				*tail = a;
-				break;
-			}
-		}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		*tail = *node;
+		tail = &(*tail)->next;
 	}
+	*tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 	return head;
 }
 
@@ -52,29 +39,17 @@ __attribute__((nonnull(2,3,4,5)))
 static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
 			struct list_head *a, struct list_head *b)
 {
-	struct list_head *tail = head;
+	struct list_head *tail = head, **node;
 	u8 count = 0;
 
-	for (;;) {
+	for (node = NULL; a && b; *node = (*node)->next) {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			tail->next = a;
-			a->prev = tail;
-			tail = a;
-			a = a->next;
-			if (!a)
-				break;
-		} else {
-			tail->next = b;
-			b->prev = tail;
-			tail = b;
-			b = b->next;
-			if (!b) {
-				b = a;
-				break;
-			}
-		}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		tail->next = *node;
+		(*node)->prev = tail;
+		tail = *node;
 	}
+	b = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 
 	/* Finish linking remainder of list b on to tail */
 	tail->next = b;

同樣的修改也適用在 `tools/lib/list_sort.c` 檔案內。

---

## 送 Patch 流程

為了送出我的 patch ，我閱讀了 Linux 核心的貢獻 patch 說明 [Submitting patches: the essential guide to getting your code into the kernel](https://docs.kernel.org/process/submitting-patches.html) ，按照說明的方式來貢獻。

跟據說明，需要透過 `git format-patch` 來讓 git 跟據 commits 來產生 patch ，故會需要先 clone Linux kernel git repository 。

### 下載最新的 Linux kernel tree

需要先 clone 最新的 Linux kernel tree 。其中可以透過 Google 提供的 Linux kernel 的 git mirror 來加速 clone 。

git clone https://kernel.googlesource.com/pub/scm/linux/kernel/git/torvalds/linux.git

### 進行修改並 commit

下載完後，我就去修改 `lib/list_sort.c` 和 `tools/lib/list_sort.c` 的程式碼。這二邊的程式基本上是相同的，但前者是用在 kernel 本身，後者用在 Linux kernel 提供的使用者模式下的工具 .

我的 commit message 如下：

lib/list_sort: eliminate if-statements in merge and merge_final

Eliminate if-statements in merge and merge_final functions by using
indirect pointers and bitwise operations.

This will make the code more elegant and reduce the number of branch
instructions.

在 commit 之前，先透過 git 命令設定自己的名字和 E-mail ，這樣才能正確出現在 commit message 中：

$ git config --global user.name "Yan-Jie Wang"
$ git config --global user.email "[e-mail]"

之後再用 `git commit -s` 來進行 commit ，特別注意 `-s` 這個參數，它會為 commit message 加入 `Signed-off-by: ....` ，`....` 是自己的名字和 E-mail ，是貢獻 Linux 核心需要加入的，代表自已對這個 commit 負責。

### 建立 Patch

Linux 核心貢獻不像 GitHub 是透過 Pull request ，是透過電子郵件寄送 patch 來貢獻。 git 提供了方便的命令 `git format-patch` 來建立 patch 。

$ git format-patch --base=auto -o patch origin/master

其中， `--base=auto` 是在 patch 中加入 base commit 的 hash ，讓開發者和 CI 工具知道你的 patch 是基於哪個 commit 建立的。 `-o patch` 用來指定 patch 檔案輸出目錄。 `origin/master` 用來告訴 git 要跟哪一個 git ref 做比較，這裡是指定 `origin/master` 也就是上游遠端的 repository 中的 master branch 。

### 寄送 E-mail

在 [Submitting patches: the essential guide to getting your code into the kernel](https://docs.kernel.org/process/submitting-patches.html) 文件，特別強調 E-mail 應以純文字寄送，不應用 MIME 格式或把 patch 放在附件。但現在的 Gmail 或是像是 Thunderbird 等軟體都會去嘗試對 E-mail 內的格式做調整，這樣核心開發者收到 patch 沒辦法直接去套用。

但還好的是 `git` 提供一個很方便的工具來寄信， `git send-email` ，透過它就不會有上述問題。 <https://git-send-email.io/> 這個網站有提供設定教學。關鍵點是在 `~/.gitconfig` 加入 SMTP 資訊，如下：

[sendemail]
	smtpserver = smtp.gmail.com
	smtpuser = [e-mail]
	smtpencryption = tls
	smtpserverport = 587
	smtpPass = ........

設定完成後，就可以來寄信了。至於要寄給誰呢? Linux 核心原始碼目錄裡，提供一個方便的工具 (`./scripts/get_maintainer.pl`) 來查詢要寄給誰。

$ ./scripts/get_maintainer.pl ./patch/0001-lib-list_sort-reduce-if-statements.patch 
Yan-Jie Wang <[e-mail]> (commit_signer:1/1=100%,authored:1/1=100%,added_lines:15/15=100%,removed_lines:40/40=100%)
[e-mail] (open list)

如上所示，要寄給 `[e-mail]` 。

:::info
在 2023/3/28 ， Jserv 老師跟我說，我應該要寄給相關的 `lib` 維護者和近期對 `lib/list_sort.c` 有較多修改的開發人員。

故上述 `./scripts/get_maintainer.pl` 是不夠的，仍然要去翻閱 Commit log 和看核心程式碼下的 `MAINTAINERS` 檔案來查詢要寄送的人員。

以 `lib/list_sort.c` 來說，還需要包含 `George Spelvin <[e-mail]>`
:::

做完設定，找出收件者，就來寄信了。寄信很簡單：

$ git send-email --to=<寄送對象> <patch 檔案> 

故我用下方命令來寄。如果怕寄錯，可以先寄給自已確認沒問題再寄出。

git send-email patch/0001-lib-list_sort-reduce-if-statements.patch --to=[e-mail]

過幾分鐘後，就可以在 Linux kernel mailing list 看到自已寄的 patch 。
我的 patch [在這](https://lore.kernel.org/lkml/[e-mail]/)。

---

## Patch 改版

第一個 patch 不是最完美的，我很快就發現我的 patch 還可以寫得更好。透過改用 `do-while` 迴圈，可以減少一個分支指令：

@@ -16,28 +16,15 @@ __attribute__((nonnull(2,3,4)))
 static struct list_head *merge(void *priv, list_cmp_func_t cmp,
 				struct list_head *a, struct list_head *b)
 {
-	struct list_head *head, **tail = &head;
+	struct list_head *head, **tail = &head, **node = NULL;
 
-	for (;;) {
+	do {
 		/* if equal, take 'a' -- important for sort stability */
-		if (cmp(priv, a, b) <= 0) {
-			*tail = a;
-			tail = &a->next;
-			a = a->next;
-			if (!a) {
-				*tail = b;
-				break;
-			}
-		} else {
-			*tail = b;
-			tail = &b->next;
-			b = b->next;
-			if (!b) {
-				*tail = a;
-				break;
-			}
-		}
-	}
+		node = cmp(priv, a, b) <= 0 ? &a : &b;
+		*tail = *node;
+		tail = &(*node)->next;
+	} while ((*node = (*node)->next));
+	*tail = (struct list_head *) ((uintptr_t) a | (uintptr_t) b);
 	return head;
 }
 

### 重新製作 Patch

修改完成後，用 `git add lib/list_sort.c tools/lib/list_sort.c` 把相關檔案加入 staging area ，然後用 `git commit --amend` 來重寫目前的 commit 。

再用 `git format-patch` 命令來建新的 patch

$ git format-patch --base=auto -o patch_v2 -v 2 origin/master

上述的 `-v 2` 代表此 patch 是第二版。執行完後，會產生 `patch_v2/v2-0001-lib-list_sort-reduce-if-statements.patch` 就是新的 patch 檔。

與前面不一樣的是，第二版以後的 patch 都要加入修改記錄，故用文字編輯器打開 patch 檔案，在 commit message 後 `---` 下方加入：

Changes since v1:
 * Use do-while instead of for-loop to avoid an unnecessory check at
   the beginning of the loop.
 * After moving *node to the next node, just check whether *node is
   NULL or not instead of checking both a && b to determine whether to
   continue.
 * Above changes further reduces the compiled code size and branch
   instructions.

### 寄送 E-mail

為了避免洗版，和讓核心開發人員可以關聯原始 patch 和新版的 patch ，要在 E-mail header 加入 In-Reply-To ， 內容是第一版的 Message ID 。故到 Linux Kernel Mailing List 查詢自已寄送 patch 的 Message ID ：

Message-ID: <[e-mail]>

或是看最下方的 Reply Instruction:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=[e-mail] \
    --to=[e-mail] \
    --cc=[e-mail] \
    /path/to/YOUR_REPLY

這裡就告訴我們怎麼用 `git send-email` 來寄送。但這裡還是要把 `to` 改成 `[e-mail]` ，而 `--cc ...` 就可以拿掉了。最後的寄送命令是：

$ git send-email \
    --in-reply-to=[e-mail] \
    --to=[e-mail] \
    patch_v2/v2-0001-lib-list_sort-reduce-if-statements.patch

這樣子第二版的 patch 就寄出了。

- [我的第二版 patch 連結](https://lore.kernel.org/lkml/[e-mail]/)
- [我的第三版 patch 連結](https://lore.kernel.org/lkml/[e-mail]/)

## 後來實測我的貢獻不好

在 3/28 ， Jserv 老師跟我討論貢獻的事時，因為我沒附上 `--cc` 至相關開發人員，他建我一段時間後再重寄 `v4` 版本，並附上實驗數據。因此我就開始做了實驗。

### 用 Compiler Explorer 確認編譯後的 Assembly Code

我在 Compiler Explorer 把 `merge` 的程式片段放進去。[連結在此](https://godbolt.org/z/vqorfz967)。
仔細推敲後，發現
* 編譯器在 `cmp(priv, a, b) <= 0 ? &a : &b` 這段程式，仍會產生分支指令，沒有辦法用沒有分支的版本來做。故我提出的修改，仍需要每個迴圈執行 2 個分支指令。
* 我提出修改的版本，比起原來版本，有更多記憶體存取。因為間接指標的緣故，編譯器需要把 `a` 和 `b` 二變數放在記憶體而不是暫存器中，導致我的版本需要更多記憶體存取。

### 用實驗來驗證效率

我把 Linux Kernel 的 `list_sort.c` 和相關 header 取出，獨立出來做實驗。

>[實驗 GitHub linux23q1-listsort_merge](https://github.com/yanjiew1/linux23q1-listsort_merge)

實驗結果如下：

**list_sort_old**

==== Testing list_sort_old ====
  Elapsed time:   932879
  Comparisons:    18687074
  List is sorted

 Performance counter stats for './main':

          2,191.79 msec task-clock                #    0.999 CPUs utilized          
                26      context-switches          #   11.862 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
            17,640      page-faults               #    8.048 K/sec                  
     3,483,542,142      cycles                    #    1.589 GHz                      (49.75%)
     1,044,185,810      instructions              #    0.30  insn per cycle           (62.34%)
       290,589,632      branches                  #  132.581 M/sec                    (62.51%)
        57,638,386      branch-misses             #   19.83% of all branches          (62.71%)
       264,842,404      L1-dcache-loads           #  120.834 M/sec                    (62.80%)
        30,758,979      L1-dcache-load-misses     #   11.61% of all L1-dcache accesses  (62.66%)
        17,525,868      LLC-loads                 #    7.996 M/sec                    (49.88%)
        10,929,504      LLC-load-misses           #   62.36% of all LL-cache accesses  (49.70%)

       2.194075207 seconds time elapsed

       2.128773000 seconds user
       0.064143000 seconds sys

**list_sort_new**

==== Testing list_sort_new ====
  Elapsed time:   968952
  Comparisons:    18687074
  List is sorted

 Performance counter stats for './main':

          2,252.19 msec task-clock                #    0.999 CPUs utilized          
                24      context-switches          #   10.656 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
            17,642      page-faults               #    7.833 K/sec                  
     3,579,407,995      cycles                    #    1.589 GHz                      (50.00%)
     1,241,668,747      instructions              #    0.35  insn per cycle           (62.60%)
       280,393,124      branches                  #  124.498 M/sec                    (62.70%)
        58,405,660      branch-misses             #   20.83% of all branches          (62.71%)
       358,193,062      L1-dcache-loads           #  159.042 M/sec                    (62.72%)
        30,661,094      L1-dcache-load-misses     #    8.56% of all L1-dcache accesses  (62.43%)
        17,743,846      LLC-loads                 #    7.879 M/sec                    (49.72%)
        11,428,072      LLC-load-misses           #   64.41% of all LL-cache accesses  (49.71%)

       2.255113789 seconds time elapsed

       2.205093000 seconds user
       0.048198000 seconds sys

果然我提出的 merge 在 cycle 數、instruction 數量，記憶體存取數及花費時間都比較慢。
故這個貢獻計畫就取消了。

### 失敗後的處理

為了避免開發者誤用 patch ，故我再寄了一封信到 Linux Kernel Mailing List 如下。

On Sat, Mar 25, 2023 at 8:32 PM Yan-Jie Wang <[e-mail]> wrote:
> 
> Reduce if-statements in merge and merge_final functions by using 
> indirect pointers and bitwise operations.
> 
> This will make the code more elegant and reduce the number of branch
>  instructions in compiled code.
> 
> Signed-off-by: Yan-Jie Wang <[e-mail]> ---

After performing some tests, I found that the merge algorithm I proposed
in this patch is not faster than the original one.

The number of branch instructions executed per loop is still the same
(two branch instructions per loop) since the compiler will generate a
branch instruction for `node = cmp(priv, a, b) <= 0 ? &a : &b;`.

In addition, there are more memory access in my proposed one because the
use of the indirect pointer, `node`, forces the compiler to put the
local variables, `a` and `b`, in memory. This will slow down the
performance.

This is the result of the compiled assembly:
   https://godbolt.org/z/vqorfz967

The test I wrote to evaluate the performance:
   https://github.com/yanjiew1/linux23q1-listsort_merge

I would like to thank Ching-Chun (Jim) Huang for providing advice for
this patch.


Yan-Jie Wang

因為這是一封回信。原本我想要直接在 Gmail 寄，但 Gmail 在寫信的過程中，因為字體不是等寬，沒辦法讓我判斷每一行的字數。後來改用 Thunderbird 這個 E-mail Client，它有 Auto Wrap 的工具，可以自動把太長的行折下來。

寄出後，沒多久，信件[就出珼在 Linux Kernel Mailing List](https://lore.kernel.org/lkml/[e-mail]/)

---

## 失敗感言與學習

至次第一分貢獻宣告失敗。

這次失敗經驗讓我學到： 不要太急著送 patch ，好好做實驗，確認提出的程式是更好的作法，且沒有問題，才發送 patch 。

真的很感謝 Jserv 老師的指導，讓我發現我提出 patch 的問題。