# 2023q1 homework1 (lab0)開發日誌
contributed by < `Urbaner3` >
:::warning
注意 GitHub 帳號名稱。我已經幫你修改了。
> [name=yanjiew1]
:::
:::info
感謝，其實我也很猶豫，那是我一開始設定的情形。
> [name=Urbaner]
:::
###### tags: `linux2022`,`linux kernel`
### Reviewed by `yanjiew1`
- commit message 語意表達不太清楚，開頭沒有大寫。例如： [c7fe7ff](https://github.com/Urbaner3/lab0-c/commit/c7fe7ff5132087ae7d32f1ff08f01d1c5f757e25) ，`implem_t del_mid ` 可改為 `Implement q_delete_mid` 。
- Coding style 沒有符合規範，建議善用 `clang-format -i` 來協助調整 Coding style 。例如下方 `q_delete_dup` 的程式：
```c=
if(strcmp(val1->value, val2->value) == 0){
list_del(val1);
q_release_element(cur);
break;
}
else
printf("mulp is %c\n",mulp);
```
5, 6 行 ： `else` 和 `}` 應為同一行； 第 1 行： `)` 和 `{` 中間要有空格。可改為：
```c=
if(strcmp(val1->value, val2->value) == 0) {
list_del(val1);
q_release_element(cur);
break;
} else
printf("mulp is %c\n", mulp);
```
- 完成度不高，沒達到作業要求，但可以從共筆中看到你的努力。未來繼續努力，加油！
## 實驗環境
```shell!
(base) urbaner@urbaner:~$ gcc --version
gcc (Ubuntu 12.2.0-3ubuntu1) 12.2.0
(base) urbaner@urbaner:~$ 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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i3-7100 CPU @ 3.90GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
Stepping: 9
CPU(s) scaling MHz: 21%
CPU max MHz: 3900.0000
CPU min MHz: 800.0000
BogoMIPS: 7799.87
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 64 KiB (2 instances)
L1i: 64 KiB (2 instances)
L2: 512 KiB (2 instances)
L3: 3 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/linux2023-lab0)
[queue.c 介面](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a#-%E6%94%B9%E5%AF%AB%E8%87%AA-CMU-%E9%9B%BB%E8%85%A6%E7%B3%BB%E7%B5%B1%E6%A6%82%E8%AB%96%E7%9A%84%E4%BD%9C%E6%A5%AD)
- `q_new`: 建立新的「空」佇列;
- `q_free`: 釋放佇列所佔用的記憶體;
- `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
︙
(後續…參閱[queue.c 介面])
## 開發過程
### 簡介：
完成作業要求，得到一個完整可控制排序的介面，包含自動偵錯、結果輸出、測試。熟悉專案開發環境，多人一起合作，認識程式從編碼，執行過程中控制，錯誤停止相關的觀念及技術等。這份作業可以輸入多個文字節點，利用 linux 內核鏈結序列結構，依照開頭順序，做需要的處理，包含排序、刪除重複、交換、翻轉順序等等。如[例題：刪除重複](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)。
[你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)，背景知識回顧: The C++ Build Process Explained 此章節有
AST 產生之程序，以利於確認所有標頭檔，如下：
```shell!
gcc -H -O0 -std=c99 -g -c -o queue.o queue.c
```
參考作業： [laneser_2022q1](https://hackmd.io/@laneser/linux2022_lab0) ，[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)
### q_new
三步驟，配置空間、檢查開頭非空、控制指標。
:::warning
建議寫清楚一點，這樣子太文言看不懂
> [name=yanjiew1]
:::
:::info
我放程式碼加上註解
> [name=Urbaner3]
:::
```cpp!
struct list_head *q = malloc(sizeof(struct list_head)) // 配置空間
if (!list_empty(q)) // 檢查開頭非空
INIT_LIST_HEAD(q); //控制指標
return q;
```
```diff
@@ -16,7 +16,8 @@
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!list_empty(q))
- INIT_LIST_HEAD(q);
+ return NULL;
+ INIT_LIST_HEAD(q);
return q;
}
```
改為 [`!q`寫法](https://github.com/yanjiew1/lab0-c/commit/0f09bf6ab87795c13f8aae2e6f773e48ce41eb0a) 通過 `make test` 測試13，原理待釐清。
### q_free
(1)element_t (2)q_release_element (3)list_for_each_entry_safe 經過兩次修改三處，閱讀並理解後，確認函數為如下：
```cpp
void q_free(struct list_head *l) {
if (l == NULL)
return;
element_t *n, *s;
list_for_each_entry_safe (n, s, l, list)
q_release_element(n);
free(l);
}
```
老師舉 yanjiew 同學的例子，讓我另一個疑惑，free 到底作用在哪個結構更有興趣去探討了。
:::warning
`free` 要作用在當初用 `malloc` 配置記憶體的結構上。故串列的頭是 `struct list_head` ，而串上去有存值的節點是 `element_t` 。
> [name=yanjiew1]
:::
### q_insert_head & tail
~~因為對list結構，只知道細節，目前當作規格一樣遵守，日後維護時一併觀察。~~ 越用越習慣了。
注意到需要用 strdup 函數，並將 insert 共用部份縮減為 part_ins 函式。
```cpp
element_t *part_ins(char *s)
{
element_t *new_ele = malloc(sizeof(element_t));
if (new_ele == NULL)
return NULL;
new_ele->value = strdup(s);
if (new_ele->value == NULL) {
free(new_ele);
return NULL;
}
return new_ele;
}
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *new_ele = part_ins(s);
if (new_ele == NULL)
return false;
list_add(&new_ele->list, head);
return true;
}
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL)
return false;
element_t *new_ele = part_ins(s);
if (new_ele == NULL)
return false;
list_add_tail(&new_ele->list, head);
return true;
}
```
:::warning
可以想想 `q_insert_tail` 可以怎麼利用 `q_insert_head` 來達成。可以參考[我寫的](https://github.com/yanjiew1/lab0-c/blob/92d98c6902dcc681297d2485141a51508100f6a3/queue.c#L70)。
> [name=yanjiew1]
:::
### q_remove_head
很疑惑 q_remove_head 函數，其中的兩個參數，{ char *sp, size_t bufsize }，還有 q_remove_head 程式碼的 macro 巨集 container_of，發現 jserv 之前有做說明 [container_of](https://hackmd.io/@sysprog/linux-macro-containerof) 附註於[你所不知道的 C 語言: linked list 和非連續記憶體(含目錄)](https://hackmd.io/@owlfox/BJkrdnExL/https%3A%2F%2Fhackmd.io%2Fs%2FSkE33UTHf#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-linked-list-%E5%92%8C%E9%9D%9E%E9%80%A3%E7%BA%8C%E8%A8%98%E6%86%B6%E9%AB%94) 另外 [linked list 案例實作](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)，這兩個連結是一樣的，但一個有包含你所不知道的 C 語言系列目錄。此處與 [link](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#%E8%BF%BD%E8%B9%A4%E8%A8%98%E6%86%B6%E9%AB%94%E9%85%8D%E7%BD%AE%E5%92%8C%E9%87%8B%E6%94%BE%E7%9A%84%E7%8B%80%E6%B3%81) 情形類似，可以注意它的插圖，幫助理解。注意有用到 strncpy 貼上 bufsize ，有些同學提到使用 memcpy 列於考慮中。[好的說明](https://hackmd.io/@Risheng/linux2023-lab0#q_remove_head)，類似複製變數值的道理，將第三個變數稱作 buffer ，最後在結尾補上0，完成刪除的動作。
```cpp!
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
element_t *n = container_of(head->next, element_t, list);
list_del(head->next);
if (sp != NULL) {
strncpy(sp, n->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return n;
}
```
:::warning
共筆中英文和中文之間要有空格。
漢語表達不太清楚。例如：「有用到 strncpy 貼上 bufsize 」這句話， 應該可以改成「使用 `strncpy` 函式，將 `n->value` 中的字串複製到 `sp` 中，最多複製 `bufsize - 1` 個字元。」。可以善用 ChatGPT 來改進。
> [name=yanjiew1]
:::
### q_remove_tail
修改一次兩處： (1)head 要做檢查。 (2)可以盡量使用 q_remove_head
因為對head的檢查，以及類似的指標是否為空，此一類檢查另我覺得很冗贅，所以思索原因並設計實驗確認，如以下，實驗方法與結果。
```shell!
(base) urbaner@urbaner:~/linux2022/lab0-c$ make SANITIZER=1
CC queue.o
queue.c: In function ‘q_new’:
queue.c:20:8: error: ‘rr’ is used uninitialized [-Werror=uninitialized]
20 | if (!rr)
| ^
queue.c:19:23: note: ‘rr’ was declared here
19 | struct list_head *rr;
| ^~
cc1: all warnings being treated as errors
make: *** [Makefile:50: queue.o] Error 1
(base) urbaner@urbaner:~/linux2022/lab0-c$ vim queue.c
```
:::warning
只看文字無法了解你想表達的意思，建議在共筆貼出此段程式碼，文字描述寫完整一點。
> [name=yanjiew1]
:::
:::info
已修正並標示下方段落。
>[name=Urbaner3]
:::
### 實驗方法與結果
```cpp!
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
puts("check if sturct initial and malloc are null");
if (q != NULL)
printf("malloc is not null\n");
else
puts("sorry, malloc is null @@");
if (list_empty(q))
puts("list is empty");
else if (list_empty(q)==0)
puts("not empty!!");
if (q != NULL)
INIT_LIST_HEAD(q);
if (q != NULL)
printf("malloc is not null\n");
else
puts("sorry, malloc is null @@");
if (list_empty(q))
puts("list is empty");
else if (list_empty(q)==0)
puts("not empty!!");
return q;
}
void q_free(struct list_head *l)
{
if (l == NULL)
return;
element_t *n, *s;
int lp_l, lp_nl;
list_for_each_entry_safe (n, s, l, list)
q_release_element(n);
raise(SIGINT);
free(l);
lp_l=list_empty(l);
if (lp_l == 0){
puts("l not empty in q_free");
}
lp_nl=list_empty(&n->list);
raise(SIGINT);
if (lp_nl == 0)
puts("n not empty in q_free");
}
```
```shell!
(base) urbaner@urbaner:~/linux2022/lab0-c$ make SANITIZER=1
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC linenoise.o
LD qtest
(base) urbaner@urbaner:~/linux2022/lab0-c$ ./qtest
cmd> new
check if sturct initial and malloc are null
malloc is not null
not empty!!
malloc is not null
list is empty
l = []
cmd>
(base) urbaner@urbaner:~/linux2022/lab0-c$ scripts/debug.py -d
Reading symbols from /home/urbaner/linux2022/lab0-c/qtest...
cmd> free
Program received signal SIGINT, Interrupt.
__pthread_kill_implementation (no_tid=0, signo=2, threadid=<optimized out>) at ./nptl/pthread_kill.c:44
```
malloc 函式初始化指標，其值為非 NULL ，這樣我們知道不需要測試，足以繼續開發。 list_empty 在 new 指令 q_new 函數前後能分別指令效果。所以應該把有關測試的檔案，其中 if(q!=NULL) 片段修改為 if(list_empty(q)) 才有意義。~~這告訴我們要習慣用 else if 來作測試，尤其是必須確認 if 條件式當中的變數值時。
於是將 q_new, q_free, q_insert_head, q_insert_tail, q_remove_head, q_remove_tail 都進行 if 條件式的修正。~~ CONTRIBUTING.md 檔案有說明，有~~比較好~~標準的 if 敘述參考。 至此完成初步操作，通過 `make check` 的要求。~~接下來的部份，會在發布前先暫時貼在這裡，通過測試後，再整理筆記。~~
:::warning
無法理解你的意思。
當 malloc 回傳值不為 NULL 時，表示空間配置成功。然而，配置的記憶體空間是未初始化的，可能包含先前該記憶體位置上的舊資料。因此，在使用前應先進行初始化。
> [name=yanjiew1]
:::
### q_delete_mid
```cpp!
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || list_empty(head)) {
return false;
}
struct list_head *h = head->next;
struct list_head *t = head->prev;
while (true) {
if (h == t || h->next == t) {
list_del(h);
q_release_element(list_entry(h, element_t, list));
break;
} else {
puts("del tail case.");
break;
}
h = h->next;
t = t->prev;
}
return true;
}
```
按照 [leetcode](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/) 的提示，刪去前方的節點。
**失敗案例**，沒定好結束條件，有最優化的程式提示錯誤：
```shell!
cmd> it tig
l = [meer dolp bea ger bea ger tig]
cmd> rt tig
Removed tig from queue
l = [meer dolp bea ger bea ger]
cmd> dm
del tail case.
l = [meer dolp bea ger bea ... ]
ERROR: Queue has more than 5 elements
cmd> show
Current queue ID: 0
l = [meer dolp bea ger bea ... ]
ERROR: Queue has more than 5 elements
```
:::warning
`h` 和 `t` 二個指標相遇時，應該要刪除 `t` 才對。
> [name=yanjiew1]
:::
:::info
已標注失敗案例，考慮今後省略，對開發無幫助，也無法交流，僅為我個人的疑慮。
下方補上程式碼。
:::
補完程式碼：
```cpp!
if (h->next == t) {
list_del(t);
q_release_element(list_entry(t, element_t, list));
break;
}
h = h->next;
t = t->prev;
```
### q_delete_dup
需要比對字串，因為 element_t 型別預設 value 為 char 型別，先指定strcmp做函數，找到三種作法，參考 [for](https://hackmd.io/@freshLiver/2022q1-hw1#%E9%87%9D%E5%B0%8D%E4%BD%87%E5%88%97%E7%9A%84%E6%93%8D%E4%BD%9C), [while](https://hackmd.io/@jim12312321/linux2022-lab0#q_delete_dup), [cut_position](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup), 可以學到不同的函式用法，能較快熟練 linked list 的細節。
:::info
縮減筆記篇幅，將疑惑與困難記錄收錄到另一份筆記。
[link: dedup](https://hackmd.io/@Urbaner/page1#delete_dup)
:::
```graphviz
digraph structs {
rankdir=LR;
node[shape=circle];
struct0 [label= "head"];
struct1 [label= "1"];
struct2 [label= "1"];
struct3 [label= "1"];
struct4 [label= "2"];
struct5 [label= "3"];
struct6 [shape=plaintext label="cut"];
struct7 [shape=plaintext label="it"];
struct8 [shape=plaintext label="safe"]
struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5;
struct7 struct6 struct8
{rank = same; struct0; struct6};
{rank = same; struct1; struct7};
{rank = same; struct2; struct8};
}
```
```graphviz
digraph structs {
rankdir=LR;
node[shape=circle];
struct0 [label= "head"];
struct1 [label= "1"];
struct2 [label= "1"];
struct3 [label= "1"];
struct4 [label= "2"];
struct5 [label= "3"];
struct6 [shape=plaintext label="cut"];
struct7 [shape=plaintext label="it"];
struct8 [shape=plaintext label="safe"]
struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5;
struct7 struct6 struct8
{rank = same; struct0; struct6};
{rank = same; struct2; struct7};
{rank = same; struct3; struct8};
}
```
```graphviz
digraph structs {
rankdir=LR;
node[shape=circle];
struct0 [label= "head"];
struct1 [label= "1"];
struct2 [label= "1"];
struct3 [label= "1"];
struct4 [label= "2"];
struct5 [label= "3"];
struct6 [shape=plaintext label="cut"];
struct7 [shape=plaintext label="it"];
struct8 [shape=plaintext label="safe"]
struct0 -> struct1 -> struct2 -> struct3 -> struct4 -> struct5;
struct7 struct6 struct8
{rank = same; struct0; struct6};
{rank = same; struct3; struct7};
{rank = same; struct4; struct8};
}
```
如圖示，保持 cut 位置，移到比對相異時，safe 的節點，分開兩個 list。按照 list_cut_position 的定義，傳入參數。
[code_page](https://github.com/Urbaner3/lab0-c/blob/b65f692d80f5dabeb08e796044e87e370231dcbf/queue.c#L139)
### swap and sort
merge_sort [node ed.](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C), [list ed.](https://npes87184.github.io/2015-09-12-linkedListSort/), [recursive](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-1)
[my work of merge sort](https://github.com/Urbaner3/lab0-c/blob/182237afbb53f941ede406a2ff93671f81284b30/queue.c#L227) 其中含有 [merge_two](https://github.com/Urbaner3/lab0-c/blob/182237afbb53f941ede406a2ff93671f81284b30/queue.c#L273) 自訂函式
[work of swap](https://github.com/Urbaner3/lab0-c/blob/182237afbb53f941ede406a2ff93671f81284b30/queue.c#L180)
```cpp!
void q_sort(struct list_head *head)
{
/* Remove every node which has a node with a strictly greater value anywhere
* to the right side of it */
/*https://npes87184.github.io/2015-09-12-linkedListSort/ */
if (!head || !head->next)
return head;
struct list_head *fast = head->next;
struct list_head *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
/*reset fast node, cut the list*/
fast = slow->next;
slow->next = NULL;
q_sort(head);
q_sort(fast);
two_merge(head, fast);
```
trace 04, 05
### reverse (and merge)
依序將節點從頭走訪，再將開頭視為另一表單入口，很像瓶口向瓶底送，先進後出，FILO。
### merge
實作時使用 list 儲存排序後結果。把 [iterative merge](https://npes87184.github.io/2015-09-12-linkedListSort/) 排序後接上，結合 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_merge_two), [alan](https://github.com/alanjian85/lab0-c/blob/master/queue.c#L183) 的作法，寫出表單版本的合併。最後考慮若迴圈結束時， l1 或 l2 為空，將剩餘表單依序接在新做表單，再去做切割。
trace 03, 05
```cpp!
static void merge_two(struct list_head *l1, struct list_head *l2){
if (!l1 || !l2)
return 0;
element_t *nod1, *nod2;
LIST_HEAD(newhd);
nod1 = list_first_entry(l1,element_t,list);
nod2 = list_first_entry(l2,element_t,list);
while (l1 && l2){
if (strcmp(nod1->value, nod2->value) < 0)
/*add l1 node to tail of newhd list */
list_move_tail(l1, &newhd);
else
list_move_tail(l2, &newhd);
}
list_splice(&newhd, l1);
list_splice(
}
```
```cpp!
struct list_head *temp = LIST_HEAD(nh);
struct list_head *q = temp;
element_t *ll1, *ll2;
while (l1 && l2) {
ll1 = list_entry(l1, element_t, list);
ll2 = list_entry(l2, element_t, list);
if (*ll1->value < *ll2->value) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
struct list_head *head = q->next;
list_del(q);
free(q);
return head;
```
釐清 queue_context 這個結構之後，可以理解 [alan](https://github.com/alanjian85/lab0-c/blob/f34b3b61b64347cc98abdbfe8b3df8dc62a97bed/queue.c#L267) 的程式碼，把 qc 命名之後，改正 size 的名字為 cnt_len，避免與 q_size 搞混。
先記錄第一列的資料，再引入迴圈，讀取第二列數列資料，合併和刪除空數列，即完成。
[work of code](https://github.com/Urbaner3/lab0-c/blob/f1a0c592b5f5cae50c71e45c39e75835a863fd9a/queue.c#L299)
### dedup reverseK, descend
trace 06
根據 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_descend) descend 為所有點右邊不可有更大的值或字串，從右邊開始，刪去小於尾端的值或字串，整理到開頭。 ascend 則相反。
[work of code](https://github.com/Urbaner3/lab0-c/blob/6b118495d9bbe9df2426e4c973c5d1f34cd4f6ef/queue.c#L256)
## Valgrind 與 自動程式設計
## Web server
```shell!
./qtest
cmd> web
listen on port 9999, fd is 3
cmd> Unknown command '.'
cmd> Unknown command 'favicon.ico'
cmd> l = []
cmd> Unknown command 'favicon.ico'
cmd> l = [1]
cmd> Unknown command 'favicon.ico'
cmd> l = [2 1]
cmd> Unknown command 'favicon.ico'
Error limit exceeded. Stopping command execution
```
[epoll_program](https://hackmd.io/@qwe661234/S1tuJOC6s#Explain-how-select-system-call-work-in-this-program-and-examine-the-consolec-implementation)
## 亂數 ＆ Dudect 論文
[chi_square_test](https://soc.utah.edu/sociology3112/chi-square.php)
[t-test](https://highscope.ch.ntu.edu.tw/wordpress/?p=73780) [excel](https://highscope.ch.ntu.edu.tw/wordpress/?p=73782)
檢查，[yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89)
/lab-0/dudect/ttest.c , only `push`, `compute` and `init`
3 functions.
/ob.../dudect/src/dudect.h, 4 `struct`s ; public,`init`,`main`,`free`, `randombits`, `randombytes`
`cmp`, `percentile`, `cpucycles()`, `measure`, `report_test`, `test` `percentile` in `dedect_ctx_t`
Sign in with Wallet
Connect another wallet