---
tags: linux2023
---
# 2023q1 Homework1 (lab0)
contributed by < `visitorckw` >
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 165
Model name: Intel(R) Core(TM) i5-10500 CPU @ 3.10GHz
Stepping: 3
CPU MHz: 3100.000
CPU max MHz: 4500.0000
CPU min MHz: 800.0000
BogoMIPS: 6199.99
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
```
## 開發過程
> Current score: 83/100
### q_new
一開始的實作如下:
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
後來想到可以寫得更精簡，當 malloc 配置記憶體成功後，才使用 `INIT_LIST_HEAD` 巨集。
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
使用 `list_for_each_entry_safe` 巨集逐一釋放每個單元占用的空間。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry;
element_t *safe;
list_for_each_entry_safe (entry, safe, l, list) {
free(entry->value);
free(entry);
}
free(l);
}
```
### q_insert_head
使用 malloc 函式去配置記憶體，若失敗就先用 free 函式釋放記憶體後 return false ，否則利用 list_add macro 來將新的節點加入到 list 之中。
原先採用 strcpy 函式進行字串的複製，但在 git commit 時會遇到以下錯誤:
```
Dangerous function detected in /home/student1/linux2023/lab0-c/queue.c
90: strcpy(sp, delNode->value);
```
因此定義了 strlcpy 巨集，在複製時需指定長度，透過改成 sprintf 函式來實作:
```c
#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif
```
最後完整的 q_insert_head 函式如下:
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newNode = (element_t *) malloc(sizeof(element_t));
if (!newNode)
return false;
newNode->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!newNode->value) {
free(newNode);
return false;
}
strlcpy(newNode->value, s, strlen(s) + 1);
list_add(&newNode->list, head);
return true;
}
```
### q_insert_tail
邏輯與 q_insert_head 函式相同。唯一的不同之處是原先使用 list_add 巨集來完成，這裡是要從尾端加入新節點，因此要改用 list_add_tail 巨集。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newNode = (element_t *) malloc(sizeof(element_t));
if (!newNode)
return false;
newNode->value = (char *) malloc(sizeof(char) * (strlen(s) + 1));
if (!newNode->value) {
free(newNode);
return false;
}
strlcpy(newNode->value, s, strlen(s) + 1);
list_add_tail(&newNode->list, head);
return true;
}
```
### q_remove_head
先用 list_entry macro 抓出將要 remove 的節點，將節點的 value 字串的內容複製給 sp 之後，再用 list_del macro 刪除。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *delNode = list_entry(head->next, element_t, list);
size_t length = bufsize < strlen(delNode->value) + 1
? bufsize
: strlen(delNode->value) + 1;
strlcpy(sp, delNode->value, length);
list_del(head->next);
return delNode;
}
```
後來發現須要先檢查 sp 的值是否是 NULL，若是 NULL則不應該將字串複製給它。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *delNode = list_entry(head->next, element_t, list);
size_t length = bufsize < strlen(delNode->value) + 1
? bufsize
: strlen(delNode->value) + 1;
if (sp && bufsize)
strlcpy(sp, delNode->value, length);
list_del(head->next);
return delNode;
}
```
### q_remove_tail
跟 q_remove_head 的邏輯相同，差在要抓的節點是 head->prev。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *delNode = list_entry(head->prev, element_t, list);
size_t length = bufsize < strlen(delNode->value) + 1
? bufsize
: strlen(delNode->value) + 1;
strlcpy(sp, delNode->value, length);
list_del(head->prev);
return delNode;
}
```
和 q_remove_head 一樣，後來加入了 sp 是否為 NULL 的檢查機制。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *delNode = list_entry(head->prev, element_t, list);
size_t length = bufsize < strlen(delNode->value) + 1
? bufsize
: strlen(delNode->value) + 1;
if (sp && bufsize)
strlcpy(sp, delNode->value, length);
list_del(head->prev);
return delNode;
}
```
### q_size
使用 list_for_each 巨集走訪整個 list 計算節點的數量。
```c=
int q_size(struct list_head *head)
{
if (!head)
return 0;
int ctr = 0;
struct list_head *node;
list_for_each (node, head)
++ctr;
return ctr;
}
```
### q_delete_mid
慢指標一次移動一格，快指標一次移動兩格。
因此當快指標走完整個 list 時，慢指標的位置會剛好只走了快指標的一半。
```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 *slow = head;
struct list_head *fast = head;
while (1) {
slow = slow->next;
if (fast->next == head || fast->next->next == head)
break;
fast = fast->next->next;
}
element_t *delNode = list_entry(slow, element_t, list);
list_del(slow);
free(delNode->value);
free(delNode);
return true;
}
```
### q_delete_dup
使用 list_for_each 巨集走訪整個鏈結串列。
額外用一個字串 str 來記錄當前節點的 value 字串內容。
並且再另外用一個 while 迴圈來找字串內容相同的元素，並使用 list_del 巨集對節點做 remove 。
- 待解決的問題: 在執行完 q_delete_dup 過後接著執行 q_free 會產生以下錯誤:
```
ERROR: There is no queue, but 3 blocks are still allocated
```
目前猜測是由於刪除時有發生 memory leak 的情形，需用 valgrind 等工具檢查錯誤產生的原因。
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return true;
struct list_head *cur;
list_for_each (cur, head) {
if (cur->next == head)
break;
element_t *L = list_entry(cur, element_t, list);
element_t *R = list_entry(cur->next, element_t, list);
if (strcmp(L->value, R->value))
continue;
char *str = (char *) malloc(sizeof(char) * (strlen(L->value) + 1));
strlcpy(str, L->value, strlen(L->value) + 1);
struct list_head *prev = cur->prev;
while (prev->next != head) {
element_t *node = list_entry(prev->next, element_t, list);
if (strcmp(str, node->value))
break;
list_del(prev->next);
free(node->value);
free(node);
}
cur = prev;
}
return true;
}
```
### q_swap
迴圈每次將指標移動兩格，將自身與下一個節點的 value 交換。
交換採用三次 bitwise xor 的技巧。
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
for (struct list_head *cur = head->next; (long int) cur ^ (long int) head;
cur = cur->next->next) {
if (cur->next == head)
return;
element_t *L = list_entry(cur, element_t, list);
element_t *R = list_entry(cur->next, element_t, list);
L->value = (char *) ((long int) L->value ^ (long int) R->value);
R->value = (char *) ((long int) L->value ^ (long int) R->value);
L->value = (char *) ((long int) L->value ^ (long int) R->value);
}
}
```
:::warning
撰寫更精簡的程式碼。
:notes: jserv
:::
修正後的程式碼如下，使用 flag 變數來記錄是否跟前一個節點交換 value 。
```c
void q_swap(struct list_head *head)
{
int flag = 0;
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head) {
if (flag & 1) {
element_t *L = list_entry(cur, element_t, list);
element_t *R = list_entry(cur->prev, element_t, list);
R->value = (char *) ((long int) L->value ^ (long int) R->value);
L->value = (char *) ((long int) L->value ^ (long int) R->value);
}
flag ^= 1;
}
}
```
### q_reverse
將所有節點的 next 和 prev 的值交換 ( 須包含 head )。
交換採用 3 次 bitwise xor 的技巧。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *cur = head;
do {
cur->prev =
(struct list_head *) ((long int) cur->prev ^ (long int) cur->next);
cur->next =
(struct list_head *) ((long int) cur->prev ^ (long int) cur->next);
cur->prev =
(struct list_head *) ((long int) cur->prev ^ (long int) cur->next);
cur = cur->prev;
} while ((long int) cur ^ (long int) head);
}
```
### q_reverseK
將每 k 個拆成一段獨立出來的 list 。
呼叫前面所實作好的 q_reverse 函式之後，再拼接回原本的鏈結串列中。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
struct list_head *ptr = head;
struct list_head *cur = head;
while (1) {
for (int i = 0; i < k; i++) {
cur = cur->next;
if (cur == head)
break;
}
if (cur == head)
break;
struct list_head *next = cur->next;
element_t ele;
struct list_head *dummy = &(ele.list);
dummy->next = ptr->next;
dummy->prev = cur;
ptr->next->prev = dummy;
cur->next = dummy;
q_reverse(dummy);
ptr->next = dummy->next;
dummy->next->prev = ptr;
dummy->prev->next = next;
next->prev = dummy->prev;
ptr = cur = dummy->prev;
}
}
```
### mergeTwoLists
由於實作 q_sort 以及 q_merge 兩個函式時都需要用到合併已排序連結串列的操作。因此額外實作本函式以利後續開發與維護。
合併兩個已經由小到大排序好的 list 合併。
採用 indirect pointer 技巧使程式碼更簡潔易讀。
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head **ptr = &L1;
struct list_head *ptr1 = L1->next;
struct list_head *ptr2 = L2->next;
while (ptr1 != L1 && ptr2 != L2) {
element_t *node1 = list_entry(ptr1, element_t, list);
element_t *node2 = list_entry(ptr2, element_t, list);
if (strcmp(node1->value, node2->value) < 0) {
(*ptr)->next = ptr1;
ptr1->prev = *ptr;
ptr1 = ptr1->next;
} else {
(*ptr)->next = ptr2;
ptr2->prev = *ptr;
ptr2 = ptr2->next;
}
ptr = &(*ptr)->next;
}
while (ptr1 != L1) {
(*ptr)->next = ptr1;
ptr1->prev = *ptr;
ptr1 = ptr1->next;
ptr = &(*ptr)->next;
}
while (ptr2 != L2) {
(*ptr)->next = ptr2;
ptr2->prev = *ptr;
ptr2 = ptr2->next;
ptr = &(*ptr)->next;
}
(*ptr)->next = L1;
L1->prev = *ptr;
return L1;
}
```
### q_sort
先利用和前面實作 q_delete_mid 所用到的快慢指針技巧找到將 list 拆分成兩半的位置。然後加入 dummy node 形成兩個獨立的 list。分別 sort 兩個list 之後，再將兩個排序好的 list 利用前面實作的 mergeTwoLists 函式合併。
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *slow = head->next;
struct list_head *fast = head->next;
while (fast->next != head && fast->next->next != head) {
slow = slow->next;
fast = fast->next->next;
}
element_t ele;
struct list_head *dummy = &(ele.list);
struct list_head *mid = slow->next;
struct list_head *last = head->prev;
mid->prev->next = head;
head->prev = mid->prev;
dummy->next = mid;
dummy->prev = last;
last->next = dummy;
mid->prev = dummy;
q_sort(head);
q_sort(dummy);
mergeTwoLists(head, dummy);
}
```
### q_descend
類似於 monotonic stack 的概念，反向迭代整個 list ，並同時記錄當前所遇到最大的 value 。若當前的 value 比過去最大的 value 還要小則利用 list_del 函式來進行 remove 的動作。
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
char str[50000] = ""; // unsafe for possible larger length
struct list_head *next;
for (struct list_head *cur = head->prev; cur != head; cur = next) {
next = cur->prev;
element_t *node = list_entry(cur, element_t, list);
if (strcmp(node->value, str) < 0) {
list_del(cur);
free(node->value);
free(node);
} else
strlcpy(str, node->value, 50000);
}
return q_size(head);
}
```
### q_merge
採用頭尾兩兩合併的方式，不斷重複直到剩下一個 list 為止。
- 待解決的問題: 在執行 make test 指令時發現，由於 merge 過後會造成當前指向的 queue 被設為 null 進而導致後續的一串指令都失效。
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return list_entry(head->next, queue_contex_t, chain)->size;
int queueSize = q_size(head);
while (queueSize > 1) {
struct list_head *node;
list_for_each (node, head) {
queue_contex_t *que1 = list_entry(node, queue_contex_t, chain);
queue_contex_t *que2 =
list_entry(head->prev, queue_contex_t, chain);
if (que1 == que2)
break;
que1->q = mergeTwoLists(que1->q, que2->q);
que2->q = NULL;
que2->size = 0;
list_del(head->prev);
}
queueSize = (queueSize + 1) / 2;
}
list_entry(head->next, queue_contex_t, chain)->size =
q_size(list_entry(head->next, queue_contex_t, chain)->q);
return list_entry(head->next, queue_contex_t, chain)->size;
}
```
### Valgrind 自動檢測
執行 ```make valgrind``` 過後，發現多數結果都如下:
```text
==616700== 2,049 bytes in 1 blocks are still reachable in loss record 46 of 47
==616700== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==616700== by 0x10C0C9: do_remove (qtest.c:373)
==616700== by 0x10C4B7: do_rh (qtest.c:463)
==616700== by 0x10E053: interpret_cmda (console.c:181)
==616700== by 0x10E623: interpret_cmd (console.c:201)
==616700== by 0x10EA60: cmd_select (console.c:610)
==616700== by 0x10F36B: run_console (console.c:705)
==616700== by 0x10D3E0: main (qtest.c:1276)
==616700==
```
代表檢測到程式結束時，仍然有著還沒被釋放的記憶體，但有指標依然指向它。可能是由於 globla 變數所導致的現象。
### q_shuffle
首先在 qtest.c 裡面增加 shuffle 命令:
```
ADD_COMMAND(shuffle, "Shuffle the queue with Fisher–Yates shuffle algorithm", "");
```
然後參考其他 `do_` 開頭的函式實作 `do_shuffle`
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!current || !current->q)
report(3, "Warning: Calling sort on null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
q_show(3);
return !error_check();
}
```
另外由於 commit hook 不允許更動 queue.h 之中的程式碼，因此另外用一個標頭檔 shuffle.h 並在裡面增加 q_shuffle 函式的宣告
```c=
#ifndef SHUFFLE_H
#define SHUFFLE_H
void q_shuffle(struct list_head *head);
#endif
```
並在 qtest.c 之中引入此標頭檔。
---
### `lib/list_sort.c`
由於 list_sort.c 程式碼中所引入的標頭檔都是 linux 核心之中的標頭檔，因此需要自己做對應的修改才能順利的執行。
:::danger
改進漢語描述，注意作業書寫規範。
:notes: jserv
:::
1. 將 u8 改為 uint8_t
2. likely 以及 unlikely 巨集是定義在 linux/compiler.h 之中的巨集，因此需要在 list_sort.h 之中自己加入以下程式碼:
```c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
```
3. 需要自己實作比較函式，如下:
```c
int cmp(void *_, const struct list_head *a, const struct list_head *b)
{
char *strA = list_entry(a, element_t, list)->value;
char *strB = list_entry(b, element_t, list)->value;
return strcmp(strA, strB);
}
```
### 論文閱讀 - Dude, is my code constant time?
* 本論文介紹了 dutect 工具，用於評估代碼在特定平台上是否以恆定時間運行，並且不需要對硬體有特別的要求。
* 方法步驟
1. Measure execution time
* 進行測量時，首先需要定義兩種不同的數據類別，一種是固定的數據類別，而另一種是隨機的數據類別。
* 現代 CPU 提供週期計數器（例如 x86 系列中的 TSC 寄存器，或 ARM 可用的 systick 外設），可用於準確地獲取執行時間測量。
* 為了最小化環境變化對結果的影響，在進行測量時，每次測量對應一個隨機選擇的輸入數據類別。類別分配和輸入準備任務在測量階段之前執行。
2. Apply post-processing
* 在進行統計分析前，應對每個單獨的測量進行一些處理。
* 典型的時序分佈對較長的執行時間呈正偏斜。這可能是由於測量數據本身的問題，或者是主進程被操作系統或其他外部因素干擾所致。因此可以捨棄大於固定閾值的測量值。
* 根據應用的統計檢驗方法，可以進行一些高階前處理。
3. Apply statistical test
* T 檢定: 可以使用 Welch’s t-test。需要注意的是，當 t 檢定與裁剪預處理結合使用時，不僅測試平均值是否相等，還測試更高階的統計矩，因為裁剪是一種非線性變換。
* 非參數檢定
* percentile 處理
percentile 是論文中步驟二所提及的 cropping 處理，目的是為了去除極值。
Sign in with Wallet
Connect another wallet