# 2025q1 Homework1 (lab0)
contributed by < `gnkuan0712` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
> 題目：[2025 年 Linux 核心設計課程作業 —— lab0 (A)](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a)
## 前置作業
### Ubuntu環境設定
有關在寫作業前的環境設定寫在這裡: [Link](https://hackmd.io/@QBDGWzPZQ8-cJhy92UlrVg/linux_hw0)
### 我注意到的細節
* Programming style
使用工具來調整作業程式要求的風格 `$ clang-format -i *.[ch]`
* 用四個空格不要用縮排 Tab
* 函式的左大括號應該放在行首( if else 那些就放在同行即可)
``` cpp
int function(int x)
{
body of function
}
```
* 正確的寫法們, 反正就是重要的字後面在空格就好
```cpp
s = sizeof(struct file);
unsigned long long memparse(char *ptr, char **retptr);
```
* Commit 基本規範
### 每次要push前的步驟
1. sudo git add `queue.c` 放要更改的檔案名稱
2. sudo git config --global user.name "Carol Chen"
3. sudo git config --global user.email gnkuan0712@gmail.com
4. sudo clang-format -i queue.c (都用這個先檢查排版？)
5. sudo git commit -a 用這個 command 直接進到類似 vim 可以修改 commit 的空間(?
這裡也可以善用 GPT 檢查 commit 寫的是否合規，最後按 ctrl + x 儲存 Enter 離開，然後就會新增了
```
Improve q_size function to handle null input
Update the q_size function so that it first checks for a null head
pointer and returns 0 when no list is provided.
```
### 執行評分
1. sudo make
2. sudo make test
3. 重整: sudo make clean
### Valgrind + 自動測試程式
`$ valgrind --tool=<toolname> <program>`
toolname 選擇: memcheck
* man strdup
#### 安裝步驟
$ sudo apt install libc6-dbg
### 可以debug的工具
先下指令 `q_test.c` , 進入cmd
```
cmd> new
l = []
cmd> ih 1
l = [1]
cmd> ih 3
l = [3 1]
cmd> shuffle
l = [1 3]
```
### 參考前一屆資料
* 先到去年[期末展示](https://hackmd.io/@sysprog/linux2024-showcase)的作品中尋找作者名字
* 然後再對應回去他們去年寫的 lab0
* 包含`Kuanch`, `weihsinyeh`, `vax-r`
* [Kuanch lab0-c](https://github.com/Kuanch/lab0-c) | [hackmd](https://hackmd.io/@Kuanch/linux2024-homework1)
* [weihsinyeh lab0-c](https://github.com/weihsinyeh/lab0-c/blob/master/queue.c) | [hackmd](https://hackmd.io/@weihsinyeh/SJUVTnEn6)
* [vax-r lab0-c](https://github.com/vax-r/lab0-c/blob/master/queue.c) | [hackmd](https://hackmd.io/@vax-r/linux2024-homework1)
## 檔案理解
* .clang-format: 確保團隊 code 風格一致
## 實作 queue.[ch]
### q_new
:::spoiler 我總共參考了三位同學的寫法
1.
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (!head || !head->prev)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
2.
```c
struct list_head *q_new()
{
struct list_head *new_q = malloc(sizeof(struct list_head));
if (new_q)
INIT_LIST_HEAD(new_q);
return new_q;
}
```
3.
```c
struct list_head *q_new()
{
struct list_head *new_qhead = malloc(sizeof(struct list_head));
if (!new_qhead)
return NULL;
INIT_LIST_HEAD(new_qhead);
return new_qhead;
}
```
:::
歸納出 q_new() 應該要直接用以下方法
* malloc() 失敗時，會直接返回 NULL
* 第二個沒有處理 Null 的狀態
* 第一個多處理 head->prev 的情況
```diff
struct list_head *q_new()
{
struct list_head *new_qhead = malloc(sizeof(struct list_head));
+ if (!new_qhead)
+ return NULL;
INIT_LIST_HEAD(new_qhead);
return new_qhead;
}
```
### q_free
:::spoiler 我總共參考了三位同學的寫法
1.
```cpp
void q_free(struct list_head *l)
{
if (!l)
return;
for (struct list_head *node = l->next, *next; node != l; node = next) {
next = node->next;
element_t *e = list_entry(node, element_t, list);
free(e->value);
free(e);
}
free(l);
return;
}
```
2.
```cpp
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, l, list) {
list_del(&(entry->list));
free(entry->value);
free(entry);
}
list_del_init(l);
free(l);
return;
}
```
3.
```cpp
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
free(entry->value);
free(entry);
}
free(l);
return;
}
```
:::
歸納出 q_free() 可以用以下方法
l 是 dummy node 用來管理整個鏈表
* list_for_each_entry_safe(entry, safe, l, list): linux kernel 提供的一個安全遍歷巨集
* entry 指向 l 的第一個節點
* 讓 safe 記住 entry->next
* entry = safe
* INIT_LIST_HEAD(l); 是一個用來初始化的巨集 (macro)
* 把l的指標 next 和 prev 都指向自己(之後 free 就會都刪掉)
* 確保 l 不再指向已釋放的記憶體
* 避免 dangling pointer
```diff
void q_free(struct list_head *l)
{
if (!l)
return; //鏈表不存在 不做後續操作
element_t *entry, *safe; //entry當前元素 //safe是entry的下一個節點
list_for_each_entry_safe(entry, safe, l, list) {
free(entry->value);
free(entry);
}
+ INIT_LIST_HEAD(l); // 清空 list，確保指標不指向已釋放的記憶體
free(l); // 釋放 list_head 本身
}
```
### q_delete_mid
```diff
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *first = head->next;
struct list_head *second = head->prev;
while ((first != second) && (first->next != second)) {
first = first->next;
second = second->prev;
}
element_t *node = list_entry(first, element_t, list);
list_del(first);
free(node->value);
free(node);
return true;
}
```
* 待補: 分析記憶體使用狀況 Massif
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
> 為一段 bottom-up mergesort 的演算法，可排序任意 struct list_head 組成的雙向循環 linked list。
## 實作 `shuffle` 命令
### 實作 Fisher-Yates shuffle Algorithm
步驟：
1. 新增 `qtest.c` 中的內容
* COMMAND
```diff
+ ADD_COMMAND(shuffle, "Fisher-Yates shuffle Algorithm", "");
```
* do_shuffle
``` diff
static bool do_shuffle(int argc, char *argv[])
{
if (!current || !current->q)
report(3, "Warning: Calling shuffle on null queue");
error_check();
if (q_size(current->q) < 2)
report(3, "Warning: Calling shuffle on single queue");
error_check();
if (exception_setup(true))
q_shuffle(current->q);
q_show(3);
return !error_check();
}
```
2. 新增 `queue.c` 中的內容
```
void q_shuffle(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
int len = q_size(head);
struct list_head *pos, *tmp;
/* Iterate over the queue backwards safe against removal of list entry */
for (pos = head->prev, tmp = pos->prev; pos != head && len;
pos = tmp, tmp = pos->prev, len--) {
struct list_head *pick = head->prev;
for (int r = rand() % len; r > 0; r--)
pick = pick->prev;
if (pick == pos)
continue;
swap(pos, pick);
}
}
```
3. 在 queue.h 新增
```
void q_shuffle(struct list_head *head);
```
#### 我的做法是參考
[前一屆 var-x 同學的github](https://github.com/vax-r/lab0-c/blob/master/queue.c)
### 統計方法驗證
新增 `shuffle.py` 是利用 [lab0-d](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-d) 提供之測試腳本進行實驗，結果如下
```shell
Expectation: 41666
Observation: {'1234': 41672, '1243': 41623, '1324': 41640, '1342': 41782, '1423': 41773, '1432': 41540, '2134': 41665, '2143': 41527, '2314': 41432, '2341': 41564, '2413': 41941, '2431': 41839, '3124': 41727, '3142': 41664, '3214': 41806, '3241': 41497, '3412': 42108, '3421': 41845, '4123': 41576, '4132': 41369, '4213': 41253, '4231': 41819, '4312': 41717, '4321': 41621}
chi square sum: 19.382278116449864
```
將以上數據作圖如下
可以觀察到 shuffle 產生的結果大致符合 uniform distribution
## 研讀論文[〈Dude, is my code constant time?〉](https://eprint.iacr.org/2016/1123.pdf)
Sign in with Wallet
Connect another wallet