# 2025q1 Homework1 (lab0)
contributed by <```ivan125126```>
### Reviewed by `salmoniscute`
程式碼的部分可以加上是使用哪個語言，舉例來說：
```c
int a;
```
[作業要求](https://hackmd.io/@sysprog/linux2025-lab0)
- [x] **GitHub 操作**
- [x] Fork `lab0-c`
- [x] 參閱 Git 教學與 GitHub 設定指引（附教學影片）
- [x] 使用 `git log` 確認出現 commit `c621c4b`
- [ ] **程式修改與測試**
- [ ] 修改 `queue.[ch]` 及相關檔案
- [x] 測試後，使用 Git 管理所有修改，確保 `$ make test` 自動評分系統通過
- [x] 在提交前，詳閱《如何寫好 Git Commit Message》
- [ ] **程式設計與優化**
- [ ] 研讀「你所不知道的 C 語言: linked list 和非連續記憶體」，並運用（例如 pointer to pointer）技巧精簡程式碼
- [ ] 參閱「2023 年 Linux 核心設計課程第一次作業檢討」及解說影片，注重細節
- [ ] 研讀 Linux 核心原始碼 `lib/list_sort.c`
- [ ] 嘗試引入專案中
- [ ] 比較自實作的 merge sort 與 Linux 核心版本效能
- [ ] 改進鏈結串列排序效能
- [ ] 詳閱改進 `lib/list_sort.c` 的解說錄影
- [ ] **qtest 命令與隨機性分析**
- [ ] 新增 `shuffle` 命令：使用 Fisher–Yates shuffle 對佇列所有節點進行洗牌，並以統計方法分析其「亂度」
- [ ] 在 qtest 中執行 `option entropy 1` 並搭配 `ih RAND 10` 等命令
- [ ] 觀察亂數字串分布
- [ ] 設計新命令或選項以切換不同 PRNG（例如 Xorshift），並利用統計工具比較亂數品質
- [ ] 閱讀參考資料：
- 「由大數法則理解訊息熵 (entropy) 的數學意義」
- 「The Linux Pseudorandom Number Generator Revisited」
- [ ] **時間複雜度與實驗驗證**
- [ ] 研讀論文〈Dude, is my code constant time?〉
- [ ] 解釋「simulation」模式如何用實驗（非理論分析）驗證時間複雜度，說明 Student's t-distribution 與程式實作原理
- [ ] 討論現有致命缺陷並提出解決方案
- [ ] **程式缺陷與改進**
- [ ] 檢查 oreparaz/dudect 中 percentile 的處理，指出 lab0-c 的缺陷或改進處（例如更全面使用 Linux 核心風格的鏈結串列 API）
- [ ] 嘗試實作改進並提交 pull request
- [ ] 若已有其他學員提交，參與討論並提出更佳方案
- [ ] **開發紀錄與工具使用**
- [ ] 建立 HackMD 筆記，記錄開發過程與 GitHub 連結，內容包括：
- [ ] 詳閱第 1 週所有教材及作業描述（各部分）的啟發與疑惑
- [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
- [ ] 使用 Valgrind 排除記憶體錯誤，並用 Massif 視覺化 simulation 過程中的記憶體使用量（設計相關實驗）
- [ ] 解釋 `select` 系統呼叫在本程式中的使用，並分析 `console.c` 實作
- [ ] 參考 CS:APP RIO 套件與 CS:APP 第 10 章提示
---
## 開發環境
```
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ 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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz
CPU family: 6
Model: 141
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
CPU(s) scaling MHz: 57%
CPU max MHz: 4600.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 384 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 10 MiB (8 instances)
L3: 24 MiB (1 instance)
```
---
## 第一個遇到的問題
當我在按照[作業要求](https://hackmd.io/@sysprog/linux2025-lab0)的指引一步步到要push上去的時候，出現了
```
$ git push
Username for 'https://github.com': ivan125126
Password for 'https://ivan125126@github.com':
remote: Support for password authentication was removed on August 13, 2021.
remote: Please see https://docs.github.com/get-started/getting-started-with-git/about-remote-repositories#cloning-with-https-urls for information on currently recommended modes of authentication.
fatal: Authentication failed for 'https://github.com/ivan125126/lab0-c/'
```
按照它提供的[網址](https://docs.github.com/get-started/getting-started-with-git/about-remote-repositories#cloning-with-https-urls)查詢後我才知道，如果當初在```clone repository```的時候用的是
```
$ git clone https://github.com/你的帳號名稱/lab0-c
```
```git```會幫你把這個```URL```存下來並稱為```origin```，按照[github官網](https://docs.github.com/get-started/getting-started-with-git/about-remote-repositories#cloning-with-https-urls)的說法
>Password-based authentication for Git has been removed in favor of more secure authentication methods.
>
這是針對```http URL```方法的，所以只要改成用```SSH URL```就沒有問題了。繼續依循著[官網](https://docs.github.com/get-started/getting-started-with-git/about-remote-repositories#cloning-with-https-urls)找到了解決方案，使用:
```
$ git remote set-url origin git@github.com:ivan125126/lab0-c
```
再重新```push```一次就沒有遇到問題了。
---
## 以chatGPT為基礎修改queue.c
>目前透過自動評分系統得到的分數是 59/100。
根據[作業要求](https://hackmd.io/@sysprog/linux2025-lab0)的內容
>台大電機系李宏毅教授對於 ChatGPT 的看法是，要善用人工智慧的成果，一旦人們得以善用，人類的書寫不該比 GPT 一類的大語言模型差。
>
所以我就來更加的「善用」人工智慧了，這是[ChatGPT](https://chatgpt.com/)的[第一次commit](
https://github.com/ivan125126/lab0-c/commit/fbd5b4bc8e9ae126dd3702b9ee3ee2ef40e5c970)還有[聊天紀錄](https://chatgpt.com/share/67c56efc-7ab4-8001-b43f-3afb52f82a3b)，自動評分拿到59分，下面我會一個個檢查```GPT```寫的函數是否還有改善空間。
### ```q_new()```
>commit:[b2eec1c](https://github.com/ivan125126/lab0-c/compare/fbd5b4bc8e9ae126dd3702b9ee3ee2ef40e5c970...b2eec1c0b365b758bdd4a07a6397b3a98742f7fe)
>
以下是```GPT```所寫：
```
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
能改善的地方就是```malloc()```在配置失敗時，就會回傳```NULL```了，不需要額外寫一個```return NULL```，於是我修改成如下：
```
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
### ```q_free()```
>commit:[69a3b35](https://github.com/ivan125126/lab0-c/compare/a74d3871f1d86991a9bb2ea3523057fe6a40a92b...69a3b3569c52902d33c3dc09f8d5af3a4412b7a3)
>
我沒有給```GPT``` ```list.h```的檔案，導致它沒有使用巨集提昇可讀性。然而，我已經附上```queue.h```，它卻沒有使用```q_release_element(element_t *e)```:
```
struct list_head *cur = head->next, *next;
while (cur != head) {
next = cur->next;
element_t *elem = container_of(cur, element_t, list);
free(elem->value);
free(elem);
cur = next;
}
```
以下是我使用預定義好的巨集以及函數後改寫：
```
element_t *elem, *tmp;
list_for_each_entry_safe (elem, tmp, head, list)
q_release_element(elem);
free(head);
```
### ```q_insert_head```
明明就是直接呼叫```q_insert_tail```，卻只有```q_insert_head```一直報```ERROR: Probably not constant time or wrong implementation```到現在還是找不出原因。
###
Sign in with Wallet
Connect another wallet