# 2024q1 Homework1 (lab0)
contributed by < [`ICARUSHERALD96500`](https://github.com/ICARUSHERALD96500/lab0-c) >
:::danger
詳閱作業說明，指定的格式中有空白字元，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 6800H with Radeon Graphics
CPU family: 25
Model: 68
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU max MHz: 4785.0000
CPU min MHz: 400.0000
BogoMIPS: 6388.18
```
## 指定的佇列操作
### 結構體
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
typedef struct {
char *value;
struct list_head list;
} element_t;
```
### `q_new`
原先對 Linux Kernel API 不熟悉，寫出 `q_new`
- 流程
1.`malloc` 分配`sizeof(struct list_head)` 大小的記憶體空間。
2.若所分配的位址 `q` 失敗，為 `NULL` ，則直接 `return q` ，`q_new`函式就會回傳 `NULL` 。
```diff
struct list_head *q = malloc(sizeof(struct list_head));
if (q) {
q->prev = q;
q->next = q;
}
return q;
```
後來發現 `list.h` 當中就有 `INIT_LIST_HEAD` 故更改為下列
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head->prev = head;
}
```
### `q_free`
```c
void q_free(struct list_head *head)
{
if (head == NULL){
return;
}
while (list_empty(head)){
struct list_head *n = head ->next;
list_del(n);
free(n);
}
free(head);
}
```
### `q_insert_head`
```diff
bool q_insert_head(struct list_head *head, char *s)
{
if (head && s){
element_t * new_element = malloc(sizeof(element_t));
if (new_element){
new_element->value = strdup(s);
if (new_element->value){
head->next = new_element;
return true;
}
else {
free(new_element);
}
}
}
else{
return false;
}
}
```
:::danger
使用 `git diff` 或 `diff` 命令來產生程式碼之間的差異列表，不要憑感覺填寫，注意位移量。
:::
對於指標是否被成功分配記憶體的條件判斷的寫法，關於 `if (head != NULL)` 以及 `if (head)` 二者間的差別，雖然效果相同，後者更為簡潔，但為求可讀與維護性。
:::danger
1. 明確指出你參考的 GitHub 帳號
2. 什麼叫做「多數會選擇」？我們本該做出更精簡更有效的程式碼，不是去迎合「多數」
:::
### `q_remove_head`
起初對於 `*head` 意思與題目誤解，導致誤以為是移除對於 `head` 前一節點的元素，寫出下列的程式碼。
導致於使用 `./qtest` 測試時反而產生把 link list tail 移除的效果。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || !list_empty(head))
return NULL;
struct list_head *rm_list_head = head->prev;
struct list_head *dummy_prev = rm_list_head->prev;
struct list_head *dummy_next = rm_list_head->next;
dummy_prev->next = dummy_next;
dummy_next->prev = dummy_prev;
element_t *rm_element = list_entry(rm_list_head, element_t, list);
if (!sp || !(rm_element->value))
return NULL;
strncpy(sp, rm_element->value, bufsize);
sp[bufsize -1] = '\0';
return rm_element;
}
```
並修正下列錯誤
```diff
- struct list_head *rm_list_head = head->prev;
+ struct list_head *rm_list_head = head->next;
```
> [commit bb0dbb1](https://github.com/sysprog21/lab0-c/commit/bb0dbb1a6afcebfff7398da067caeacbf6a0b29d)
熟悉linux kernel API並修正函式中不必要的 `list` 宣告
在當中發現 `list_del`
```diff
@@ -76,16 +74,18 @@ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
+ element_t *f = list_first_entry(head, element_t, list);
+ list_del(&f->list);
- struct list_head *rm_list_head = head->next;
- struct list_head *dummy_prev = rm_list_head->prev;
- struct list_head *dummy_next = rm_list_head->next;
- dummy_prev->next = dummy_next;
- dummy_next->prev = dummy_prev;
+ if (sp) {
+ size_t copy_size =
+ strlen(f->value) < (bufsize - 1) ? strlen(f->value) : (bufsize - 1);
+ strncpy(sp, f->value, copy_size);
+ sp[copy_size] = '\0';
+ }
+ return f;
- element_t *rm_element = list_entry(rm_list_head, element_t, list);
- if (!sp || !(rm_element->value))
- return NULL;
- strncpy(sp, rm_element->value, bufsize);
- sp[bufsize - 1] = '\0';
- return rm_element;
}
```
### `q_remove_tail`
使用與 `q_remove_head` 相同邏輯
```c
if (!head || !list_empty(head))
return NULL;
struct list_head *rm_list_head = head->prev;
struct list_head *dummy_prev = rm_list_head->prev;
struct list_head *dummy_next = rm_list_head->next;
dummy_prev->next = dummy_next;
dummy_next->prev = dummy_prev;
element_t *rm_element = list_entry(rm_list_head, element_t, list);
if (!sp || !(rm_element->value))
return NULL;
strncpy(sp, rm_element->value, bufsize);
sp[bufsize -1] = '\0';
return rm_element;
```
> [commit bb0dbb1](https://github.com/sysprog21/lab0-c/commit/bb0dbb1a6afcebfff7398da067caeacbf6a0b29d)
同樣修正與函式`q_remove_head`中同樣不必要的 `list` 宣告
```diff
@@ -93,16 +93,18 @@ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
+ element_t *f = list_first_entry(head, element_t, list);
+ list_del(&f->list);
- struct list_head *rm_list_head = head->next;
- struct list_head *dummy_prev = rm_list_head->prev;
- struct list_head *dummy_next = rm_list_head->next;
- dummy_prev->next = dummy_next;
- dummy_next->prev = dummy_prev;
+ if (sp) {
+ size_t copy_size =
+ strlen(f->value) < (bufsize - 1) ? strlen(f->value) : (bufsize - 1);
+ strncpy(sp, f->value, copy_size);
+ sp[copy_size] = '\0';
+ }
+ return f;
- element_t *rm_element = list_entry(rm_list_head, element_t, list);
- if (!sp || !(rm_element->value))
- return NULL;
- strncpy(sp, rm_element->value, bufsize);
- sp[bufsize - 1] = '\0';
- return rm_element;
}
```
### `q_delete_mid`
在 `make test` 中出現 `ERROR: Removed value gerbil != expected value bear`。發現是在走訪到中間節點過程中使用 `for()` 迴圈使用錯誤導致函數輸出不為所求。修正確定其為走訪到 mid point，並改為使用 `while` 使之更為簡短。
```diff=
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
int count = q_size(head) / 2;
struct list_head *temp = head->next;
- for (int i = 0; i <= count; i++) {
+ while (count--) {
temp = temp->next;
}
list_del(temp);
q_release_element(list_entry(temp, element_t, list));
return true;
}
```
### `q_swap`
首先我嘗試的方法使用,在每兩個節點中進行 `next` 與 `prev` 之間的關係互換
```c
if (!head || list_empty(head))
return;
int count = 0;
struct list_head *node, *prev_node, *dummy_prev, *dummy_next;
for (node = (head)->next; node != (head); node = node->next) {
count++;
if (count % 2 == 0) {
prev_node = node->prev;
//
dummy_prev = prev_node->prev;
dummy_next = node->next;
dummy_prev->next = node;
dummy_next->prev = prev_node;
//
node->prev = dummy_prev;
node->next = prev_node;
//
prev_node->prev = node;
prev_node->next = dummy_next;
}
}
```
但在該方法下會產生的問題是 head 所指向的節點會因為 prev 與 next 關係重組而被排列到最後。效果如下：
```
new l = [1 2 3 4 5 6 7]
swap l = [2 3 4 3 7 6 1]
```
熟悉kernel api後改進：
> commit [b18ff64]()
```diff
@@ -226,22 +226,13 @@ void q_swap(struct list_head *head)
if (!head || list_empty(head))
return;
int count = 0;
- struct list_head *node, *prev_node, *dummy_prev, *dummy_next;
- for (node = (head)->next; node != (head); node = node->next) {
+ struct list_head *node, *prev = head;
+ list_for_each (node, head) {
count++;
if (count % 2 == 0) {
- prev_node = node->prev;
- //
- dummy_prev = prev_node->prev;
- dummy_next = node->next;
- dummy_prev->next = node;
- dummy_next->prev = prev_node;
- //
- node->prev = dummy_prev;
- node->next = prev_node;
```
### `q_reverse`
### Valgrind + 自動測試程式
閱讀 'qtest命令直譯器的實作'，發現其中展示qtest原理，展示在 qtest.c 當中的 `init_cmd()` 添加：
```c
bool do_hello(int argc, char *argv[])
{
return (bool) printf("Hello, World\n");
}
```
結果 `make` 後產生下列錯誤代碼:
```bash
/usr/bin/ld: queue.o: in function `do_hello':
/home/b37265417/linux2024/lab0-c/queue.c:390: multiple definition of `do_hello'; console.o:/home/b37265417/linux2024/lab0-c/console.c:417: first defined here
collect2: error: ld returned 1 exit status
make: *** [Makefile:49: qtest] Error 1
```
將 `bool do_hello(int argc, char *argv[])` 改為 `static bool do_hello(int argc, char *argv[])` 後解決。
## Fisher–Yates shuffle
### 將 shuffle 引入 `qtest` 命令中
參照自動測試程式在qtest新增shuffle功能，在 `console.h` 的巨集中：
```c
/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
要添加新命令需要透過在 `console.c` 底下的 `console_init` 當中使用 `add_cmd` 函式。該函式需要輸入三個引數 `"<instruction>"`、`<do_*>`、`"<document>"`。以呼叫同樣宣告在`console.c` 底下命名為 `do_<instruction>` 的函式（因為在巨集中 `do_##cmd` 將所要呼叫的函式名稱 concatinate 為 cmd 前加上 `do_`）。
以 `q_new` 函式被呼叫的流程為例。首先 `qtest.c` 的主函式中， `init_cmd()` 使用 `ADD_COMMAND` 將 `q_new()` 加入。`add_cmd` 接收的第二項引數是型別為 `cmd_func_t` 的函式指標。該指標指向 `console.c` 的 Build-in funciton 或 `qtest.c` 的 `do_*` 函式，如 `do_new()`，再由該函式中呼叫在 `queue.c` 中所撰寫的各項 `q_*` 函式。
將 `shuffle` 分別新增在 `init_cmd` 與 `console_init` 底下的的差別似乎不大，同樣都可以執行。但最後決定添加在 `console` 底下，因為其他鏈結串列的操作同樣新增在這個類別。
**qtest.c**
```c
static void consloe_init()
{...
ADD_COMMAND(shuffle, "Fisher-Yates shrffle", "")
...
}
```
```c
static bool do_shuffle(int argc, char *argv[])
{
if (!current || !current->q)
return;
if (q_size(current->q) < 2)
return;
if (exception_setup(true))
q_shuffle(current->q);
q_show(3);
return !error_check();
}
```
**queue.h**
```c
void q_shuffle(struct list_head *head) ;
```
**queue.c**
```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);
}
void q_shuffle(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
struct list_head *last = head;
int size = q_size(head);
while (size > 0) {
int index = rand() % size;
struct list_head *new = last->prev;
struct list_head *old = new;
while (index--)
old = old->prev;
swap(new, old);
last = last->prev;
size--;
}
return;
}
```
### `shuffle`
## 研讀 Linux 核心原始程式碼 list_sort.c
- [ ] 研讀 Linux 核心原始程式碼 list_sort.c
- [ ] 嘗試引入 Linux 核心原始程式碼到 lab0-c 專案
- [ ] 比較自己實做的merge sort 和 Linux 核心程式碼之間的效能落差
### 引入 Linux list_sort.c 到 lab0-c
修改檔案： `qtest.c`、`Makefile`
新增檔案： `list_sort.c`、`list_sort.h`
**list_sort.c**
為了要讓 `./qtest` command line 當中的 `time` 指令可以執行 linux `list_sort` 的方法，利用首先在 lab0-c中新增 [`list_sort.c`](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) ，並移除不會用到的部份：
:::spoiler
```c
// SPDX-License-Identifier: GPL-2.0
// #include <linux/bug.h>
// #include <linux/compiler.h>
// #include <linux/export.h>
// #include <linux/string.h>
// #include <linux/list_sort.h>
// #include <linux/list.h>
...
// EXPORT_SYMBOL(list_sort);
```
:::
**list_sort.h**
其中包含 `list_sort.c` 所需要的定義
:::spoiler
```c
#ifndef _LIST_SORT_H
#define _LIST_SORT_H
#include <stdint.h>
#include "list.h"
#define USE_LINUX_SORT 0
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
#endif /* End of _LIST_SORT_H_ */
```
:::
**Makefile**
為了使 `make` 時連同 `list_sort` 加入源代碼文件的目標編譯文件，所需更改：
```
OBJS := qtest.o report.o console.o harness.o queue.o list_sort.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
linenoise.o web.o \
```
**qtest.c**
在 `qtest.c` 中建立函式：
```c
__attribute__((nonnull(2,3)))
int cmp(void *priv, const struct list_head *list1, const struct list_head *list2)
{
element_t *list1_entry = list_entry(list1, element_t, list);
element_t *list2_entry = list_entry(list2, element_t, list);
return strcmp(list1_entry->value, list2_entry->value) < 0 ? 0 : 1;
}
```
### 比較自己的merge sort 和 Linux 核心程式碼之間的效能落差
新增一筆測資 `trace-sort.cmd` 於 `trace/` 中：
```
option fail 0
option malloc 0
new
ih RAND 10000
time
sort
time
```
並將 `Makefile` 中 check 的部份改為下列。執行 `make check` 時，便會使用自己定義的 `trace-sort.cmd` 測資。
```
check: qtest
./$< -v 3 -f traces/trace-sort.cmd
```
結果如下：
| 資料總數 | q_sort() 測試1(s) | q_sort() 測試2(s) | q_sort() 測試3(s) | q_sort() 測試4(s) | q_sort() 測試5(s) |
| -------- | ----------------- | ----------------- | ----------------- | ----------------- | ----------------- |
| 100000 | 0.08 | 0.076 | 0.078 | 0.075 | 0.076 |
| 300000 | 0.302 | 0.309 | 0.316 | 0.309 | 0.313 |
| 500000 | 0.614 | 0.585 | 0.578 | 0.576 | 0.585 |
| 資料總數 | list_sort() 測試1(s) | list_sort() 測試2(s) | list_sort() 測試3(s) | list_sort() 測試4(s) | list_sort() 測試5(s) |
| -------- | ----------------- | ----------------- | ----------------- | ----------------- | ----------------- |
| 100000 | 0.108 | 0.055 | 0.054 | 0.056 | 0.055 |
| 300000 | 0.180 | 0.178 | 0.179 | 0.178 | 0.180 |
| 500000 | 0.303 | 0.311 | 0.305 | 0.304 | 0.308 |
比較 `q_sort` 、 `list_sort` 性能差異：
## 閱讀論文 Dude, is my code constant time?
論文提出一種測試程式執行時間是否為 constant time 的工具 dudect，這個方法不需要硬體模型，以消弭不同硬體架構下對測量的影響。目的是驗證理論上時間複雜度為 constant time ，但實則存在 time leakage 的問題，如此可以藉由程式處理不同輸入時的響應時間差，藉此推敲程式內部細節，引發資安疑慮。
文中取 '字串比較' 典型場景。普遍作法為逐字元比較，若一但遇到不相符者即刻中斷比較並回傳`false` ，如此便可以透過從輸入字元到回傳的時間推敲是第幾個字元錯誤。較佳的作法為，就算遭遇不相符，也同樣比對完剩餘字元，以此避免time leakage。
作者採取 Students' T test 其中 Two-sample T test 進行實驗。使用兩種測資，第一種為全數固定為某值的固定測資、第二種為亂數的隨機測資。在虛無假設下進行 Fix-vs-Random test。
## 參考資訊
* [Risheng1128](https://hackmd.io/@Risheng/linux2022-lab0)
* [Laneser](https://hackmd.io/@laneser/linux2022_lab0)
Sign in with Wallet
Connect another wallet