# 2024q1 Homework1 (lab0)
contributed by < `LIAO-JIAN-PENG` >
### Reviewed by `lintin528`
在有多個節點被移動的狀況，像是 `q_reverseK` ，我的做法通常會是直接在原本的鏈結串列中使用 `list_move` 去做移動，這樣可以避免 `cut` 跟 `splice` 的使用，還有一個額外的 `list_head` 結構 `buf` ，這樣的話除了交換的動作外會多花費一些計算量，但這麼做的缺點就是程式的可讀性不如目前的做法，我認為這邊可以做一下取捨。
## 開發環境
```
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 3
CPU max MHz: 4300.0000
CPU min MHz: 800.0000
BogoMIPS: 5799.77
Virtualization: VT-x
L1d cache: 192 KiB (6 instances)
L1i cache: 192 KiB (6 instances)
L2 cache: 1.5 MiB (6 instances)
L3 cache: 12 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
```
## 佇列實作
:::danger
「作」是古老的字，甲骨文時代就存在，最初的涵義是「起」，現代漢語裡仍然使用的「振作」、「一鼓作氣」、「槍聲大作」中的「作」，都是「[起](https://dict.revised.moe.edu.tw/dictView.jsp?ID=6299)」的意思。在這個意義上跟「做」不衝突，因為「做」無此含義。「做」是後造字，始於宋元時代，當「即使」、「播弄」、「做作」講。
依據中華民國教育部《重編國語辭典修訂本》:
* 「[作](https://dict.revised.moe.edu.tw/dictView.jsp?ID=9622)」: 創作。如：「寫作」、「作畫」、「作詩」。《論語．述而》：「述而不作，信而好古」
* 「[做](https://dict.revised.moe.edu.tw/dictView.jsp?ID=9643)」: 製造。如：「做衣服」、「做鞋子」
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
目標：完成 `queue.c` 尚未完成的程式實作
### q_new
```diff
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
+ if (!new)
+ return NULL;
INIT_LIST_HEAD(new);
return new;
}
```
根據 C 語言規格書[7.22.3]，如果記憶體空間不足以配置，則函式應該回傳 NULL。
> If the space cannot be allocated, a null pointer is returned.
### q_swap
使用 `list.h` 的 `list_move` 可以精簡原本程式碼。
```diff
void q_swap(struct list_head *head)
{
- struct list_head *prev = head;
- struct list_head *curr = head->next;
-
- while (curr != head) {
- prev->next = curr->next;
-
- curr->prev = prev->next;
- curr->next = prev->next->next;
-
- prev->next->next = curr;
- prev->next->prev = prev;
- prev = curr;
- curr = curr->next;
+ struct list_head *li = head->next;
+ while (li != head && li->next != head) {
+ list_move(li, li->next);
+ li = li->next;
}
}
```
### q_reverse
使用 `list_move` 精簡程式碼。
```diff
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
- struct list_head *prev = head;
- struct list_head *curr = head->next;
- while (curr != head) {
- curr->prev = curr->next;
- curr->next = prev;
- prev = curr;
- curr = curr->prev;
- }
- curr->prev = curr->next;
- curr->next = prev;
+ struct list_head *li;
+ list_for_each (li, head->prev)
+ list_move(head->prev, li);
}
```
### q_reverseK
:::danger
應使用 `git diff` 或 `diff -u` 命令來產生程式碼之間的變更列表，不要憑感覺填入，注意位移量。
:::
```diff
/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head)
return;
- int times = q_size(head) / k;
+ int times = q_size(head) / (k + !k);
struct list_head *tail;
LIST_HEAD(tmp);
LIST_HEAD(new_head);
for (int i=0; i < times; i++) {
int j = 0;
list_for_each(tail, head) {
if (j >= k)
break;
j++;
}
list_cut_position(&tmp, head, tail->prev);
q_reverse(&tmp);
list_splice_tail_init(&tmp, &new_head);
}
list_splice_init(&new_head, head);
}
```
當 k 為 0 時，k + !k 會變成 0 + !0，也就是 0 + 1，其結果為 1。這樣的修正將導致當 k 為 0 時，程式碼將會計算 q_size(head) / 1，而不是 q_size(head) / 0，這可以避免浮點例外的錯誤。
> 參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework1#q_reverseK)
:::warning
本頁面的目的就是「開發紀錄」，你應該針對子主題去闡述
:::
## 研讀 lib/list_sort.c
### merge_final
```c
do {
/*
* If the merge is highly unbalanced (e.g. the input is
* already sorted), this loop may run many iterations.
* Continue callbacks to the client even though no
* element comparison is needed, so the client's cmp()
* routine can invoke cond_resched() periodically.
*/
if (unlikely(!++count))
cmp(priv, b, b);
b->prev = tail;
tail = b;
b = b->next;
} while (b);
```
這段程式碼中的 `if (unlikely(!++count))` 在 `count` 變為 0 時會執行 `cmp()` 函式。這段程式碼用於處理合併過程中可能的高度不平衡情況。在這裡，我們設置了一個 8-bit 的 `count` 變數。當 `count` 的值增加到非常大，導致溢位並變為 0 時，即使在實際上不需要進行元素比較，仍然會執行 `cmp()` 函式。
client 代表呼叫這段程式碼的外部程式的部分。當程式碼運行到某個情況時，即使不需要進行元素比較，也會持續向 client 發送 callback，以便外部的 `cmp()` 函式可以週期性地呼叫 `cond_resched()` 函式。
>Long-running list_sort() calls: If the list passed in may be long, or the
>client's cmp() callback function is slow, the client's cmp() may
>periodically invoke cond_resched() to voluntarily yield the CPU. All
>inner loops of list_sort() call back to cmp().
`cond_resched()` 的主要目的之一是讓長時間執行的核心程式碼暫時讓出 CPU ，給其他更高優先權的工作機會執行。因此在核心中有可能長時間迴圈執行的程式碼，插入 `cond_resched()` 呼叫，避免獨占住 CPU 資源。<s>這樣做是為了讓客戶端的 `cmp()` 函式能夠定期呼叫`cond_resched()` </s> 。
:::danger
不要「[舉燭](https://dict.revised.moe.edu.tw/dictView.jsp?ID=158282)」！你將註解翻譯成中文字，然後就懂了嗎？排序的程式碼裡頭出現 "client", "cond_resched", "periodically" 等字樣，你難道不會懷疑自己根本沒懂註解和程式碼的關聯嗎？
使用 `git blame` 和 `git log` 去探索這段程式碼和註解背後的演化過程，推敲後寫下你的洞見和疑惑。真正限制你專業成長的因素，就是「不懂裝懂」。
:::
```c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
`__builtin_expect()` 是 gcc 的內建函式 [GCC 手冊 __builtin_expect](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fexpect)，用來告訴編譯器我們期望的條件。編譯器會根據`__builtin_expect()` 提供的資訊，告訴CPU可能執行的分支方向。這樣 CPU 的 branch predictor 就可以根據這些提示，~~提前做出預測出下一道指令~~。這裡 `!!(x)` 的兩個 `!` 是透過兩次的 `NOT` 來確保值一定是 0 或 1。
Branch prediction 是現代 CPU 中一種重要的性能優化技術。由於 CPU 執行指令是按順序執行的，當遇到條件分支指令(比如 if-else 條件式)時，就需要決定接下來執行哪個分支。CPU 在執行到分支指令前，往往無法確定要執行哪個分支，因此需要等待分支條件被評估之後才能決定。採用 branch prediction 可以根據歷史執行記錄，提前預測和預取下一條指令的執行路徑，以避免 CPU 在執行分支指令時發生暫停。
`likely()` 巨集表示 x 為真的機率比較大，並告訴 complier 將 `x==true` 的條件對應程式碼放在判斷式後面，反之 `unlikely()` 則是 x 為假的機率比較大，並告訴 complier 將 `x==false` 的條件對應程式碼放在判斷式後面，以提高 branch prediction 的效率。
思考：cond_resched() 在沒有 kernel preemption 狀況下，效力是否等於 sched_yield()
:::warning
上面敘述不精準，對照看 GCC 手冊和計算機組織/結構教科書裡頭關於 branch prediction 的解說。
:::
## 課程教材發現與洞見
連結：[課程教材疑惑與洞見](https://hackmd.io/@Jpeng/linux2024-question)
Sign in with Wallet
Connect another wallet