---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < `JoshuaLee0321` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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: 43 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 2600X Six-Core Processor
CPU family: 23
Model: 8
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
Frequency boost: enabled
CPU max MHz: 3600.0000
CPU min MHz: 2200.0000
BogoMIPS: 7199.10
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht
```
## 目前分數
<s>
目前分數 100/100
都卡在一些memory的分配問題
2023/2/23 由於課程時發現 C 語言的前置處理器可用來定義 function-like macro，從而使程式碼更容易維護，所以本日會專注在定義macro
2023/2/27 完成 delete_dup
2023/2/27 make valgrind 中出現非常多錯誤，目前正在debug
2023/2/27 由於 `memcpy` 會報錯，所以把所有有關於 `memcpy` 的都改成 `strncpy`
</s>
:::warning
HackMD 提供時間戳記，不需要自行列舉。
注意作業書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
> 好的
:::
## 開發 `queue.c` 的過程
### `q_new`
* 首先利用 `malloc` 分配空間給queue，考量到`malloc`有機會出錯，那先判斷是不是沒有分配成功，之後再利用 Linux 核心中的 `INIT_LIST_HEAD` 來把指針指向自己
:::spoiler
```c
struct list_head *q_new()
{
struct list_head *head = malloc(1 * sizeof(struct list_head));
if(!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
:::
### `q_free`
* 最剛開始的寫法，利用 `list_for_each_safe` run 過所有的 item，一個一個節點 release 但這樣會出先 segmentation fault
:::danger
改進你的漢語描述。
:notes: jserv
:::
:::spoiler
```c
void q_free(struct list_head *l)
{
if (!l || list_empty(l)) {
free(l);
return;
}
struct list_head *it,*safe;
list_for_each_safe(it, safe, l){
element_t *tmp = list_entry(it, element_t, list);
list_del(it);
free(tmp);
}
free(list_entry(l, element_t, list));
return;
}
```
:::
:::info
後續改成 `q_release_element` 的內建API
:::
```c
void q_free(struct list_head *l)
{
if(!l || list_empty(l)) return;
// ~~ struct list_head *it, *safe;
// list_for_each_safe(it, safe, l){
// q_release_element(it);
// }~~
/*以上為錯誤版本，已修正成以下版本*/
list_for_each_entry_safe(it, safe, l, list) {
q_release_element(it);
}
free(l)
}
```
更正版本：
`element_t *it = NULL, *safe = NULL;`
`list_for_each_entry_safe(it, safe, l, list) {
q_release_element(it);
}`
:::info
(更新)發現 safe 並沒有初始化成NULL 導致出錯，已修正
(更新)發現 list_for_each_entry_safe 以及 q_release_element 才可以把東西刪除完全
:::
### `q_insert_head` `q_insert_tail` `q_delete_head` `q_delete_tail`
:::info
(更)剛開始的實做如下，但這樣會發生我的實做並不是constant time，錯誤還有代釐清
(更)以上課後學習到的新知 (macro) function 為基準 重新製作了 q_insert_##type 在macro 中
(更)已把 q_insert 以及 q_remove 類型的都把它做成macro 方便維護，除此之外還找到了 `q_remove_macro` 中少加入 if(list_empty(head)) 而導致 `segmentation fault`
:::
#### macro 如下
:::spoiler
```c
#define q_insert_macro(type, func) \
bool q_insert_##type(struct list_head *head, char *s) \
{ \
if (!head) \
return false; \
element_t *new_node = malloc(1 * sizeof(*new_node)); \
if (!new_node) \
return false; \
new_node->value = malloc((strlen(s) + 1) * sizeof(char)); \
if (!new_node->value) { \
q_release_element(new_node); \
return false; \
} \
memcpy(new_node->value, s, strlen(s) + 1); \
func(&new_node->list, head); \
return true; \
} \
#define q_remove_macro(type, func) \
element_t *q_remove_##type(struct list_head *head, char *sp, \
size_t bufsize) \
{ \
if (!head || list_empty(head)) \
return NULL; \
element_t *del = func(head, element_t, list); \
list_del(&del->list); \
if (sp != NULL) { \
memcpy(sp, del->value, bufsize - 1); \
sp[bufsize - 1] = '\0'; \
} \
return del; \
}
```
:::
而實際上我就可以只利用四行程式碼來實作
:::success
```c
/* Insert an element at head of queue */
q_insert_macro(head, list_add);
/* Insert an element at tail of queue */
q_insert_macro(tail, list_add_tail);
/* Remove an element from head of queue */
q_remove_macro(head, list_first_entry);
/* Remove an element from tail of queue */
q_remove_macro(tail, list_last_entry);
```
:::
* 如此一來 insert_head 跟 insert_tail 都可以在組譯階段被完成，如此一來可以節省空間之外還可以更好的維護兩個function
* 不過目前還在找出為甚麼此function 無法在constant time 完成，之後會研讀論文
### `q_delete_dup`
* 利用 `linux/list.h` 中的 API 跑過迴圈；要注意的事情是，這個function 必須把重複的東西通通刪除掉。由於`list_for_each_safe` 中的 `safe` 可以當作 `next` 來使用，如此一來我們只要
1. 跑過 `head` 中的所有元素
2. 使用 iterator `it` 來觀察是否當前元素與下個元素相同
3. 利用 `bool not_finished` 變數來記錄是否要把當前 `it` 刪除
以下為實作code
:::spoiler
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_is_singular(head))
return false;
struct list_head *it, *safe = NULL;
bool not_finished = false;
list_for_each_safe (it, safe, head) {
element_t *prev = list_entry(it, element_t, list);
element_t *cur = list_entry(safe, element_t, list);
if (!strcmp(prev->value, cur->value)) {
not_finished = true;
list_del(it);
q_release_element(prev);
if (safe->next == (head)) {
list_del(safe);
q_release_element(cur);
break;
}
} else if (not_finished) {
not_finished = false;
list_del(it);
q_release_element(prev);
}
}
return true;
}
```
:::
### `q_size`
* 已經由 `jserv` 老師撰寫好了
```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_delete_mid`
* 基本上這個題目有兩種作法，一種先找出 `queue` 的長度除以2之後給定一個`int cnt` 去計算這個list目前到哪裡，但這個實做方法有一個問題，它會花到O(2N)的時間
* N = 得到 `size` 的時間
* N = traverse 到中間的時間
* 第二個作法就是利用兩種不同方向或速度的指標，而我的實做方法就是利用一個每一次只會往後走一歩的 `single_p` 以及每一次會往後走兩步的 `double_p`，在double走到底的時候single會直接在中間
* 如此一來只需要直接把 `single_p` 給移除掉即可
:::spoiler
```c
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 *single_p, *double_p;
single_p = double_p = head->next;
while(double_p != (head) && double_p->next != (head)) {
single_p = single_p->next;
double_p = double_p->next->next;
}
list_del_init(single_p);
q_release_element(list_entry(single_p,element_t,list));
return true;
}
```
:::
### `q_swap`
* 在 `swap-nodes-in-pairs` 中，可以使用 `iterative` 跟 `recursive` 的方法實做，而因為有linux kernel 的 API，我選擇使用 `iterative` 的作法
* 使用 `it` 當作 每一次走過的node
* 每次 `it` 往前走一步
* 每次 `it` 跟 `it->next` 互換
如此一來就可以達到每兩個 node 互相交換了
:::spoiler
```c
void q_swap(struct list_head *head)
{
if(!head || list_empty(head) || head->next->next == head) return;
struct list_head *it = head->next;
while(it != (head) && it->next != (head)) {
list_move(it,it->next);
it = it->next;
}
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
```
:::
### `q_reverse`
* `q_reverse` 如果使用 Linux 核心的 api 就會非常簡單
* 儘需要走過這整個串列，並且每一次都把當前的node放到最前方即可
```c
void q_reverse(struct list_head *head)
{
if(!head || list_empty(head) || list_is_singular(head)) return;
struct list_head *it, *safe = NULL;
list_for_each_safe(it, safe, head) {
list_move(it, head);
}
return;
}
```
### `q_sort`
* 參考[你所不知道的 c 語言: linked list 和非連續記憶體及 Linked List Sort](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 中提到的Merge Sort ，並以 [LiChiii](https://hackmd.io/@NYC6Z-WqQ3W-61xcE-2SvA/SJDBv7Cps#q_sort) 的程式碼為實作。
## `Valgrind`
```shell
# Explicitly disable sanitizer(s)
$ make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/joshua/linux2023/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o shannon_entropy.o linenoise.o web.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC shannon_entropy.o
CC linenoise.o
CC web.o
LD qtest
make[1]: Leaving directory '/home/joshua/linux2023/lab0-c'
cp qtest /tmp/qtest.83iQ10
chmod u+x /tmp/qtest.83iQ10
sed -i "s/alarm/isnan/g" /tmp/qtest.83iQ10
scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind -t <tid>
```
## debug 紀錄
#### 2 / 23
:::info
目前一直卡在 q_insert 的function 並沒有在constant time 處理完畢
除此之外，每一次free佇列都會發生一些問題
(更新) 發先是 q_free 中的safe 沒有初始化
:::
#### 2 / 27
:::info
測試時一直發現 trace - 17 一直報告不是常數時間。同時我也很確定我的實作方法為constant time，而經由閱讀 [KHLEE](https://hackmd.io/@KHLee529/linux2023-lab0) 的實作方法，更改了 dudect/constant.c 以及 dudect/fixture 的計算方法後才得到目前的滿分
:::
Sign in with Wallet
Connect another wallet