# 2024q1 Homework1 (lab0)
contributed by <`pine0113`>
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ 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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz
CPU family: 6
Model: 167
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU max MHz: 4900.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
```
## 針對佇列操作的程式碼實作
#### `q_new`
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if(head){
INIT_LIST_HEAD(head);
return head;
}
free(head);
return NULL;
}
```
假設 head 配置成功的機率比較高，將成功的情境放在前面
但<s>感覺</s> 這種程度的優化其實 compiler 就會處理掉才對
:::danger
工程人員說話要精準，避免說「感覺」。
:::
> 修正為 TODO:
> 測試配置成功情境放置在前後的效能差異
- [ ] 測試配置成功情境放置在前後的效能差異
#### `q_free`
- [x] 檢查 l 是否為 null
```c
if(!l)
return;
```
- [x] 將佇列中所有東西移除及釋放記憶體
```c
struct list_head *cur = NULL, *safe = NULL;
list_for_each_safe (cur, safe, l)
q_release_element(container_of(cur, element_t, list));
```
#### `q_insert_head`
commit 的時候發生以下錯誤訊息
```
queue.c:60:5: error: Memory leak: new_node [memleak]
```
發現是因為在建立 new_node 的時候少做了 INIT_LIST_HEAD
而在下方直接對鏈結串列進行操錯導致
```c
element_t *new_node = malloc(sizeof(element_t));
if (!new_node) {
free(new_node);
return NULL;
}
INIT_LIST_HEAD(&new_node->list);
...
new_node->list.next = head->next;
new_node->list.prev = head;
head->next = &(new_node->list);
```
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
Bug: 第一次執行 `q_insert_tail` 時舊的資料並沒有保留在佇列中
由於原本自己寫的程式漏寫了一條指標<s>賦值</s> 導致的異常，改用 `list_add` 之後突然正常了回頭去比較兩者之間差異，
:::danger
翻閱英漢辭典，assign 何時叫做「賦值」，此處就是指派，注意書寫。
:::
```c
new_node->list.next = head->next;
new_node->list.prev = head;
head->next = &(new_node->list);
```
``` c
next->prev = node; <-- 漏的是這條
node->next = next;
node->prev = head;
head->next = node;
```
#### `q_insert_tail`
用類似 `q_insert_head `的方式完成
使用 `list_add_tail` 取代直接操作
- [x] 重構 q_insert_tail & q_insert_head
#### `q_remove_head` & `q_remove_tail`
`char *sp, size_t bufsize` 的用途待確認
目前只有使用 `list_last_entry` 跟 `list_first_entry` 將節點取出後使用 `list_del` 移除節點
根據 `queue.h` 的定義
由於 `remove` 與 `delete` 不同，所以被移除的字串需要複製到 `*sp`
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
Bug: 目前有記憶體沒有正常釋放的問題
```
ERROR: There is no queue, but 6 blocks are still allocated
```
<s>
</s>
:::danger
文字訊息避免用圖片來表示，否則不好搜尋和分類
:::
修正：使用 list_del_ini
```
list_del_init(head->next);
```
#### `q_size`
目前是作業要求內教學的版本尚未修改
```c
int q_size(struct list_head *head)
{
if (!head) return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
#### `q_ascend` & `q_descend`
使用同一個方式，把 head 視做左側、 tail 視作右側，
從右側往左側逐一確認是否需要將節點移除掉即可
#### `q_delete_mid`
在看[快慢指標](https://hackmd.io/NDN4SlBNQvCVZZ1YgYBtHg)之前，就先寫了分別從前後往中間靠攏找中間點的方式。
目前不知道哪樣實作比較好，先列入 todo
TODO:
- [ ] 分析快慢指標跟兩邊夾的方式哪種比較好
#### `q_swap`
#### `q_reverse`
#### `q_reverseK`
#### `q_sort`
#### `q_merge`
#### `q_delete_dup`
* 目前實作完所有佇列操作，由於最後的 qtest 效能評估並沒有達到預期指標，所以得 95 分，根據說明文字了解是因為單一操作的時間複雜度實際上沒有到 O(1) ，
<s>
</s>
:::danger
文字訊息避免用圖片來表示，否則不好搜尋和分類
:::
## 以 Valgrind 分析記憶體問題
> [name=pine0113]
> 幾乎把佇列實作完才回頭看這個要求
> 發現自己之前在除錯的時候都是使用迂迴的將程式區塊刪除比對來找出錯的位置。 但是 core dump 或是 segmentation fault 這類記憶體出錯的問題理應直接使用分析工具直面問題、而非用大量的時間用不正確的工具來除錯
> 幻滅是成長的開始 :notes: jserv
### 透過 Massif 視覺化 "simulation" 過程中的記憶體使用量
### 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作
* 說明其中運用 CS:APP RIO 套件 的原理和考量點。
## 研讀並引入 lib/list_sort.c
TODO ：作業說明的頭兩句 bottom up 跟 top down 的差異
* [Linux 核心排序實作的演進](https://hackmd.io/@sysprog/linux2024-lab0-e#Linux-%E6%A0%B8%E5%BF%83%E6%8E%92%E5%BA%8F%E5%AF%A6%E4%BD%9C%E7%9A%84%E6%BC%94%E9%80%B2) 章節有完整說明
<s>
</s>
:::danger
文字訊息避免用圖片來表示，否則不好搜尋和分類
:::
> 此段文這樣列出來應該是四種實作 (3+開發者提出)
> top-down、bottom-up、queue、開發者提出
### 查看 lib/list_sort.c 程式碼
TODO: 用以下檢查程式碼取代自己撰寫的相同用途程式碼前置檢查
```c
if (list == head->prev) /* Zero or one elements */
return;
```
看不懂以下區塊
```c
__attribute__((nonnull(2,3,4)))
```
* 看 `vax-r` 作業時發現他有寫到
> 首先 __attribute__((nonnull(2,3,4))) 可以參照 6.30 Declaring Attributes of Functions 的解說
> [name=pine0113]我看了他貼的連結後仍然不知道要如何由原本的程式找到對應的規格文件，這部分應該要在修正，從 gcc 文件上層也無法往下搜尋，應該是找尋的方法有問題
- [ ] 確認如何查詢 gcc 官方規格
https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/
> 發現自己有不想讀懂程式碼，想直接引用的傾向
- [ ] 重新閱讀 https://hackmd.io/@sysprog/linux2024-lab0-e#list_sort
### 引入 lib/list_sort.c 到 queue.c 中 以及效能評估
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
- [x] 引入 lib/list_sort.c
- 此處參考了 [var-x 的 作法](https://hackmd.io/@vax-r/linux2024-homework1#%E5%BC%95%E5%85%A5-list_sort-%E5%88%B0-lab0-c-%E7%95%B6%E4%B8%AD)
- [x] 修改 queue.c 加入 q_list_sort()
- 移除 priv
- [此處](https://hackmd.io/@sysprog/linux2024-lab0-e#list_sort)有提到 priv 並不會被用到
- [x] `cmpfunc` 不知道該怎麼寫
- [x] 修改 queue.h 加入 q_list_sort
- [x] 修改 qtest.c 加入 do_list_sort()
- [x] 修改 qtest.c 加入 `ADD_COMMAND(list_sort, "Sort queue with linux kernel sort", "");`
- [x] error
```
queue.c: In function ‘merge_final’:
queue.c:331:21: error: implicit declaration of function ‘unlikely’ [-Werror=implicit-function-declaration]
331 | if (unlikely(!++count))
| ^~~~~~~~
```
在 queue.h 中加入
```
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
```
- [ ] 查詢 likely 的定義應該是在[這裡](https://github.com/torvalds/linux/blob/master/include/linux/compiler.h)，但在 queue.h 中 #include <linux/compiler.h> 會有以下錯誤，先用網路上找到的方法來繞過這個問題，但要目前還無法使用正確的 include 引入對應資源
- [x] commit 時發現 被告警不能修改 queue.h
將 queue.h 的宣告分別放回 queue.c 跟 qtest.c 最上方
但這個方式是否合理需要再確認
> [name=pine0113]
> 此處是使用暴力手寫引入，有考慮是否要用 include list_sort.c/h 的方式改 compiler make 的方法，但不知道實際要做哪些步驟
有看到 @chiangkd 的[做法](https://hackmd.io/@vax-r/linux2024-homework1#%E5%BC%95%E5%85%A5-list_sort-%E5%88%B0-lab0-c-%E7%95%B6%E4%B8%AD)但尚未仔細閱讀
- [x] 了解評估效能方式項目
* 由 [Linux 核心專題: 改進 lib/list_sort.c](https://hackmd.io/@sysprog/Hy5hmaKBh) 得知有以下幾種指標
* 執行時間
* 比較次數
* Cache miss ratio
- [ ] 評估效能實作
- [ ] 執行時間計算
- [ ] 尋找用 qtest 的來計時
```
option fail 0
option malloc 0
new
ih RAND 1000000
time
sort
time
```
- [ ] 如何以大量的次數計時
- [ ] 比較次數計算
- [ ] 以 Valgrind 分析 cache miss ratio
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
## 亂數+研讀論文〈Dude, is my code constant time?〉
### qtest shuffle實作
- [x] 新增 qtest.c shuffle 命令
- [x] 實作 do_shuffle()
* 這裡實作的方式 最後參考了 willwillhi1 的程式 https://hackmd.io/@willwillhi/lab0-2023#%E5%9C%A8-qtest-%E6%96%B0%E5%A2%9E-shuffle-%E5%91%BD%E4%BB%A4
>在實作 swap 時要注意 :
node_1 總是在 node_2 之後
當兩個要交換的節點是相鄰時不要做 list_move(node_2, node_1_prev)，因為 node_1_prev 等於 node_2，如果做了 list_move(node_2, node_1_prev) 會把 node_2 這個節點移除。
>
主要是自己寫出來的 swap 犯了上面說的這點的問題但是自己找不出原因
最後再看到他的筆記的時候才發現是這個問題...
```c
static inline void swap(struct list_head *node_1, struct list_head *node_2)
{
if (node_1 == node_2)
return;
struct list_head *node_1_prev = node_1->prev;
struct list_head *node_2_prev = node_2->prev;
if (node_1->prev != node_2)
list_move(node_2, node_1_prev);
list_move(node_1, node_2_prev);
}
```
### 比較亂數產生器的品質
- [ ] 執行 lab0 (D) 的測試程式
這邊在執行的時候由於沒有任何 output，只能等待結果
用 top 來觀察程式是否有在執行，但這沒辦法判斷是否正常執行
- [x] TODO: 確認是否是程式異常或是提出修正方式
- 確認為程式異常，有機率會吃掉 node
- 使用較小的測資筆數去確認程式跑的狀況
- [ ] 執行 lab0 (D) 的繪圖程式
### 解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析
### 改進 dudect 實作
在作業提示中有提到
`在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無`
https://github.com/oreparaz/dudect/blob/master/src/dudect.h
直接進程式碼看果然是完全看不懂的，但由於作業繳交時限將至，這邊將後續想要完成的項目列在下方：
- [ ] 閱讀論文
- [ ] 重新閱讀 ＠25077667 的實作說明跟提出修正的部分
- https://hackmd.io/@25077667/SkpLspWnT#%E6%94%B9%E9%80%B2-dudect-%E5%AF%A6%E4%BD%9C
## 改善 qtest web 後 linenoise 無法正常運作
### 閱讀作業說明
根據作業要求這段文字，用搜尋的在檔案中搜尋不到 linenoiseEdit()，目前比對原始檔案後猜測應該是
`linenoise.c` 的 `static int line_edit()`
但比對程式碼後跟後面的描述感覺並不相符
`上述程式碼已整合進 qtest，可在終端機執行以下命令:`
嘗試執行 ./qtest 的 web 命令後
嘗試 `curl http://localhost:9999/new` 可以正常操作
- [ ] 修正 favicon
- [ ] 使用 web 命令後, linenoise 的 function不正常 的修正
#### Reference
* [25077667](https://hackmd.io/@25077667/SkpLspWnT)
* [Slipet](https://hackmd.io/@Slipet/ryrLNN4Ah)
* [han1018](https://hackmd.io/@zRlFO_buT66gBhkP4gN7vg/linux2024-homework1)
* [var-r](https://hackmd.io/@vax-r/linux2024-homework1)
:::warning
以第一手材料為主，注意上述學員的筆記可能存在錯誤，你需要提出修正和調整。
:::
:::danger
:warning: 留意詞彙的使用：
* [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
* [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)
* 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
Sign in with Wallet
Connect another wallet