---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < `as200188` >
## 開發環境
作業系統: ubuntu 22.04
硬體配置
```shell
$ 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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU max MHz: 4200.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
a cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss
ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art
arch_perfmon pebs bts rep_good nopl xtopology nonstop_
tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cp
l vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid ss
e4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes
xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_f
ault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_sh
adow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adj
ust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx sma
p clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dt
herm ida arat pln pts hwp hwp_notify hwp_act_window hwp
_epp md_clear flush_l1d arch_capabilities
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 8 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
Vulnerabilities:
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Mitigation; PTE Inversion; VMX conditional cache flushe
s, SMT vulnerable
Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Meltdown: Mitigation; PTI
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Retbleed: Mitigation; IBRS
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer
sanitization
Spectre v2: Mitigation; IBRS, IBPB conditional, RSB filling, PBRSB-
eIBRS Not affected
Srbds: Mitigation; Microcode
Tsx async abort: Mitigation; TSX disabled
```
## 開發過程
### 設定開發環境
#### 安裝及設定 git
參考 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github)
#### 複製 lab0-c 專案
1. Fork [lab0-c](https://github.com/sysprog21/lab0-c) 參考[官方文檔 Fork 的方式](https://docs.github.com/en/get-started/quickstart/fork-a-repo)
2. 將專案複製到本地端
```shell
$ git clone https://github.com/as200188/lab0-c.git
```
3. 設定成SSH連線 參考 [git push without password](https://stackoverflow.com/questions/6565357/git-push-requires-username-and-password)
```shell
$ git remote set-url origin git@github.com:as200188/lab0-c.git
```
4. 確認輸出
```shell
$ git remote -v
origin git@github.com:as200188/lab0-c.git (fetch)
origin git@github.com:as200188/lab0-c.git (push)
```
#### 安裝 make 套件
1. 安裝
```shell
$ sudo apt-get install make
```
2. 確認安裝版本
```shell
$ make -version
GNU Make 4.3
Built for x86_64-pc-linux-gnu
Copyright (C) 1988-2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
```
#### 安裝 curl 套件
1. 安裝
```shell
$ sudo apt-get install curl
```
2. 測試
```shell
$ curl -I https://www.gnu.org/
HTTP/1.1 200 OK
Date: Tue, 21 Feb 2023 09:29:21 GMT
Server: Apache/2.4.29
Content-Location: home.html
Vary: negotiate,accept-language,Accept-Encoding
TCN: choice
Strict-Transport-Security: max-age=63072000
X-Frame-Options: sameorigin
X-Content-Type-Options: nosniff
Access-Control-Allow-Origin: (null)
Accept-Ranges: bytes
Cache-Control: max-age=0
Expires: Tue, 21 Feb 2023 09:29:21 GMT
Content-Type: text/html
Content-Language: en
```
#### 安裝 gcc 套件
1. 安裝
```shell
$ sudo apt-get install gcc
```
2. 確認版本
```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.
```
### 測試 lab0-c 專案
#### 編譯
```shell
~/linux2023/lab0-c$ make
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
```
#### 清除編譯產生的檔案
```shell
~/linux2023/lab0-c$ make clean
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 *~)
```
### 實做 queue 相關函式
#### 實做所使用的資料結構
參考 [linked list](https://hackmd.io/@sysprog/c-linked-list)
利用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 建立雙向 linked list
#### Linked list element
想法: 節點嵌入結構體 list_head，若要取得節點，則利用 container_of 來取得節點。
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
#### Queue 結構
```c
typedef struct {
int size;
struct list_head head;
} queue_t;
```
#### 建立 element 並初始化
想法: 用 malloc() 取得節點空間，並且初始化，回傳該節點位址。
```c
/* Initial element */
static inline void INIT_ELEMENT(element_t *e)
{
e->value = NULL;
INIT_LIST_HEAD(&e->list);
}
/* Create element and initial it */
struct element_t *element_new()
{
element_t *e = malloc(sizeof(element_t));
INIT_ELEMENT(e);
return e;
}
```
未考慮到 malloc() 可能會回傳 NULL，因此將程式碼修正成:
```c
static inline void INIT_ELEMENT(element_t *e)
{
if (e == NULL)
return;
e->value = NULL;
INIT_LIST_HEAD(&e->list);
}
```
#### q_new
想法: 建 empty queue，並且做初始化。
```c
struct list_head *q_new()
{
/* Create queue and initial it */
queue_t *q = malloc(sizeof(queue_t));
q->size = 0;
INIT_LIST_HEAD(&q->head);
return &q->head;
}
```
未考慮到 malloc() 可能會回傳 NULL，因此將程式碼修正成:
```c
/* Initial queue */
static inline void INIT_QUEUE(queue_t *q)
{
if (q == NULL)
return;
q->size = 0;
INIT_LIST_HEAD(&q->head);
}
/* Create an empty queue and initial it */
struct list_head *q_new()
{
/* Create queue and initial it */
queue_t *q = malloc(sizeof(queue_t));
INIT_QUEUE(q);
return (q != NULL) ? &q->head : NULL;
}
```
#### q_insert_head
想法: 建立新節點，利用 list_add 加到第一個節點。
考慮到傳入空指標和極長字串會導致程式出錯，利用計算字串長度再加一(放空字元)，作為放字串的空間，從靜態改成動態，避免極長字串導致程式出錯，將程式碼修改成:
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
char *str = malloc(strlen(s)+1);
element_t *e = element_new();
queue_t *q = container_of(head, queue_t, head);
strcpy(str, s);
e->s = str;
list_add(&e->list, head);
q->size += 1;
return true;
}
```
發現字串動態配置空間和複製字串可由 strdup 一次做完(參考 [willwillhi](https://hackmd.io/@willwillhi/lab0-2023))，可將程式碼經簡化，將程式碼改成:
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
char *str = strdup(s);
element_t *e = element_new();
queue_t *q = container_of(head, queue_t, head);
e->value = str;
list_add(&e->list, head);
q->size += 1;
return true;
}
```
未考慮到 malloc 失敗後，未將已配置空間釋放，導致 memory leak。修正成:
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
char *str = strdup(s);
if (str == NULL)
goto malloc_failed;
element_t *e = element_new();
if (e == NULL)
goto malloc_failed;
queue_t *q = container_of(head, queue_t, head);
e->value = str;
list_add(&e->list, head);
q->size += 1;
return true;
malloc_failed:
if (str)
free(str);
if (e)
free(e);
return false;
}
```
#### q_insert_tail
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL || s == NULL)
return false;
char *str = strdup(s);
if (str == NULL)
goto malloc_failed;
element_t *e = element_new();
if (e == NULL)
goto malloc_failed;
queue_t *q = container_of(head, queue_t, head);
e->value = str;
list_add_tail(&e->list, head);
q->size += 1;
return true;
malloc_failed:
if (str)
free(str);
if (e)
free(e);
return false;
}
```
#### q_size
想法: 有一種做法是計算節點數量，然後回傳答案，但該方式的時間複雜度為 $O(N)$，我希望讓時間複雜度為 $O(1)$，所以我會有一個 queue 結構，裡面會有 size 和 head 成員，並且利用 container_of 來取得該 queue 結構。
```c
int q_size(struct list_head *head)
{
if (head == NULL)
return -1;
queue_t *q = container_of(head, queue_t, head);
return q->size;
}
```
#### q_remove_head
想法: 若能移去節點，需要將字串複製到 sp, 並將 q->size 減一。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || sp == NULL || q_size() == 0)
return NULL;
element_t *e = list_first_entry(head, element_t, list);
queue_t *q = container_of(head, queue_t, head);
strncpy(sp, e->value, bufsize-1);
sp[bufsize-1] = '\0';
list_del(&e->list);
q->size -= 1;
return e;
}
```
#### q_remove_head
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (head == NULL || sp == NULL || q_size() == 0)
return NULL;
element_t *e = list_last_entry(head, element_t, list);
queue_t *q = container_of(head, queue_t, head);
strncpy(sp, e->value, bufsize-1);
sp[bufsize-1] = '\0';
list_del(&e->list);
q->size -= 1;
return e;
}
```
#### q_free
想法: 利用 list_for_each_safe 逐一走訪 list 上的節點，利用 container_of 取得 element 並釋放該 element 所使用的空間，走訪完後，將 queue 所使用的空間釋放。
```c
void q_free(struct list_head *head)
{
if (head == NULL)
return;
queue_t *q = container_of(head, queue_t, head);
struct list_head *iter = NULL, *next = NULL;
element_t *e = NULL;
list_for_each_safe(iter, next, head){
e = container_of(iter, element_t, list);
free(e->value);
e->value = NULL;
list_del_init(iter);
free(e);
}
free(q);
}
```
由於刪除 element 這段程式經常重複，所以將該段程式寫成 function，修改成:
```c
/* Delete element and update list and queue */
static void element_del(element_t *e, struct list_head *head)
{
if (e == NULL || head == NULL)
return;
queue_t *q = container_of(head, queue_t, head);
free(e->value);
e->value = NULL;
list_del_init(&e->list);
free(e);
q->size -= 1;
}
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if (head == NULL)
return;
queue_t *q = container_of(head, queue_t, head);
struct list_head *iter = NULL, *next = NULL;
element_t *e = NULL;
list_for_each_safe (iter, next, head) {
e = container_of(iter, element_t, list);
element_del(e, head);
}
free(q);
}
```
#### q_delete_mid
想法: 有想到三種做法，第一種是逐一走訪，計算節點數，再去刪中間。第二種是用快慢指標來去找中間。第三種做法是從頭尾逐一走訪來找中間，採用第三種做法，當節點數是奇數的時候，front 等於 end時，front 和 end 都是中間節點，節點數為偶數的時候，front->next 等於 end時，end 為中間節點，找到中間節點後，將其刪除。
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (head == NULL || q_size(head) == 0)
return false;
struct list_head *front = head->next, *end = head->prev;
element_t *e = NULL;
while(front != end && front->next != end){
front = front->next;
end = end->prev;
}
e = container_of(end, element_t, list);
element_del(e, head);
return true;
}
```
#### q_reverse
想法: 有想到兩種做法，一種是不改變節點 list 指向的位址，藉由改變 value 來做到 reverse，好處是 element 只有 value 要改變時，需要交換的值很少，效率佳，可從頭尾指標做 swap，得到結果。此處使用第二種做法，改變 list 指向的位址，逐一走訪節點，將節點放到尾巴，得到結果。
```c
void q_reverse(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *old_front = head->next, *old_end = head->prev;
struct list_head *iter = NULL, *next = NULL, *tmp = NULL;
list_for_each_safe (iter, next, head) {
tmp = iter->prev;
iter->prev = iter->next;
iter->next = tmp;
}
head->next = old_end;
head->prev = old_front;
}
```
#### q_swap
想法: 兩個節點以上才需要 swap，在做 swap 時，要將前一個和下一個和下兩個的節點，指標關係需要做更新，而當 swap 時，是和最後一個節點交換，需要更新 head 的前一個節點。
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *iter = NULL, *next = NULL, *next_next = NULL,
*prev = NULL;
for (iter = head->next, next_next = iter->next->next;
iter != head && iter != head->prev;
iter = next_next, next_next = iter->next->next) {
prev = iter->prev;
next = iter->next;
iter->next = next_next;
next_next->prev = iter;
prev->next = next;
next->prev = prev;
next->next = iter;
iter->prev = next;
if (head->prev == next)
head->prev = iter;
}
}
```
#### compare
```c
int compare(const void *a, const void *b)
{
const struct list_head *a_list = a;
const struct list_head *b_list = b;
element_t *a_e = container_of(a_list, element_t, list);
element_t *b_e = container_of(b_list, element_t, list);
return strcmp(a_e->value, b_e->value);
}
```
#### q_sort
想法: 有想到兩種有效率的排序方式，quick sort 和 merge sort，怕會有 worst case 造成 quick sort 時間複雜度為 $O(N^2)$，所以最後採用 merge sort 讓時間複雜度為 $O(N*log(N))$。
```c
void merge(struct list_head *head,
struct list_head *left_head,
struct list_head *right_head)
{
struct list_head *left_iter = left_head->next,
*right_iter = right_head->next;
struct list_head *left_next = left_iter->next,
*right_next = right_iter->next;
while (left_iter != left_head || right_iter != right_head) {
if (left_iter == left_head) {
list_move_tail(right_iter, head);
right_iter = right_next;
right_next = right_iter->next;
continue;
}
if (right_iter == right_head) {
list_move_tail(left_iter, head);
left_iter = left_next;
left_next = left_iter->next;
continue;
}
if (compare(left_iter, right_iter) < 0) {
list_move_tail(left_iter, head);
left_iter = left_next;
left_next = left_iter->next;
} else {
list_move_tail(right_iter, head);
right_iter = right_next;
right_next = right_iter->next;
}
}
}
void merge_sort(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
LIST_HEAD(left_head);
LIST_HEAD(right_head);
struct list_head *front = head->next, *end = head->prev, *mid = NULL;
struct list_head *iter = NULL, *next = NULL;
while (front != end && front->next != end) {
front = front->next;
end = end->prev;
}
mid = end;
for (iter = head->next, next = iter->next; iter != mid;
iter = next, next = iter->next) {
list_move_tail(iter, &left_head);
}
for (iter = mid, next = iter->next; iter != head;
iter = next, next = iter->next) {
list_move_tail(iter, &right_head);
}
merge_sort(&left_head);
merge_sort(&right_head);
merge(head, &left_head, &right_head);
}
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
merge_sort(head);
}
```
#### q_reverseK
想法: 將 list 切成多個 group，每個 group 大小為 k，切好後利用 q_reverse() 來得到結果，最後將多個 group 拼接起來。
```c
/* 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 == NULL || list_empty(head) || list_is_singular(head))
return;
int num_of_groups = q_size(head) / k;
int i = 0, j = 0;
struct list_head *iter = head->next, *next = iter->next;
LIST_HEAD(res_head);
for (; i < num_of_groups; i++) {
LIST_HEAD(tmp_head);
for (j = 0; j < k; j++) {
list_move_tail(iter, &tmp_head);
iter = next;
next = iter->next;
}
q_reverse(&tmp_head);
list_splice_tail(&tmp_head, &res_head);
}
list_splice(&res_head, head);
}
```
#### q_delete_dup
想法: first 指標指向第一個節點，second 指標指向第二個節點，若兩個節點的字串相同，則 second 往下一個節點走，直到兩個節點的字串不相同，便能得到 first 和 second 的前一個為相同字串的節點。若兩個節點的字串不相同，first 和 second 皆往下一個節點走。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (head == NULL || list_empty(head) || list_is_singular(head))
return false;
struct list_head *first = head->next, *second = first->next,
*second_next = second->next, *first_prev = NULL;
element_t *e = NULL;
while (first != head && second != head) {
if (compare(first, second) == 0) {
first_prev = first->prev;
while (second != head && compare(first, second) == 0) {
e = container_of(second, element_t, list);
element_del(e, head);
second = second_next;
second_next = second->next;
}
e = container_of(first, element_t, list);
element_del(e, head);
first_prev->next = second;
second->prev = first_prev;
}
first = second;
second = second_next;
second_next = second->next;
}
return true;
}
```
#### q_descend
想法: 由後往前逐一走訪，紀錄當前最大值，只要比最大值小，將該節點移除即可。
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (head == NULL || list_empty(head) || list_is_singular(head))
return 0;
struct list_head *iter = head->prev, *prev = iter->prev, *max = iter;
element_t *e = NULL;
while (iter != head) {
if (compare(iter, max) > 0)
max = iter;
else if (compare(iter, max) < 0) {
e = container_of(iter, element_t, list);
element_del(e, head);
}
iter = prev;
prev = iter->prev;
}
return q_size(head);
}
```
Sign in with Wallet
Connect another wallet