HackMD2025q1 Homework1 (lab0)
contributed by < salmoniscute >
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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.
$ 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: 11th Gen Intel(R) Core(TM) i7-11370H @ 3.30GHz
CPU family: 6
Model: 140
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 1
CPU(s) scaling MHz: 20%
CPU max MHz: 4800.0000
CPU min MHz: 400.0000
BogoMIPS: 6604.80
行前準備
看原始碼的心得
在著手改動程式前，先研究原始碼來理解作業的內容。
queue.c 的實作將使用以下資料結構：
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
可以看到有 Linux 中用於實作雙向鏈結串列的
struct list_head, 以及另外三種自行定義的結構，分別都置入了 list_head 物件。在執行 qtest.c 時會藉由呼叫 q_init 來初始化雙向鏈結陣列 chain, 並且透過呼叫 do_{命令} 函式（e.g. do_new, do_ih）來進行後續操作。
為了讓自己更快理解作業的目標，我先參考 trace-01-ops.cmd 中的測資，然後再多執行一次 do_new 來畫出預期的樣子。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
可看出作業是要實作由一個雙向鏈結串列所串連在一起的多個環狀佇列，但這時候疑問來了，我不知道為什麼資料結構要這樣設計，以及為什麼 queue_contex_t 所指向的環狀佇列開頭會是 list_head 的結構而不是直接用 element_t。
於是我重新閱讀教材 〈 你所不知道的 C 語言: linked list 和非連續記憶體 〉和 〈 Linux 核心原始程式碼巨集: container_of 〉，發現上述疑惑的解答都在裡面了，真的只有自己在學習過程中囫圇吞棗、自以為已經理解的問題。
到目前為止我明白本次作業應該主要是操作 struct list_head 以及運用已經寫好的 List API 。
todo：用 Graphviz 畫圖
重要工具
實作指定佇列操作
q_insert_head , q_insert_tail
我本來是用 strcpy 搭配 malloc 來達成題目「 explicitly allocate space and copy the string into it 」的要求。結果在提交程式碼的時候出現錯誤，表示 strcpy 是 dangerous function。
Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/salmon/linux2025/lab0-c/queue.c
40: strcpy(new_element->value, s);
60: strcpy(new_element->value, s);
我改成 strncpy 搭配 malloc, 並且在最後加上 '\0' 確保字串確實終止。再次嘗試 commit 就可以了。
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new_element = malloc(sizeof(element_t));
if (!new_element)
return false;
size_t len = strlen(s) + 1;
new_element->value = malloc(len * sizeof(char));
if (!new_element->value) {
q_release_element(new_element);
return false;
}
- strcpy(new_element->value, s);
+ strncpy(new_element->value, s, len - 1);
+ new_element->value[len - 1] = '\0';
list_add(&new_element->list, head);
return true;
}
還可以再修正：
參考〈 你所不知道的 C 語言：技巧篇 〉教材中追蹤物件配置的記憶體部分有介紹到 strdup
複製字串可用 strdup 函式：
char *strdup(const char *s);strdup 函式會呼叫 malloc 來配置足夠長度的記憶體，當然，你需要適時呼叫 free 以釋放資源。
看起來可以一步完成記憶體配置和字串複製，而且不用自行計算字串的長度以及添加終止字符，更加符合優雅的程式碼撰寫方式。
q_free
沒通過靜態程式分析，這是習慣不佳導致的疏失，未符合在最小 scope 內宣告變數的規範。
Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:30:16: style: The scope of the variable 'element' can be reduced. [variableScope]
element_t *element;
^
Fail to pass static analysis.
void q_free(struct list_head *head)
{
if (!head)
return;
struct list_head *pos, *safe;
- element_t *element;
list_for_each_safe (pos, safe, head) {
- element = list_entry(pos, element_t, list);
+ element_t *element = list_entry(pos, element_t, list);
q_release_element(element);
}
free(head);
}
q_delete_mid
我原本的程式碼沒有考慮到佇列中含有偶數個 element_t 的情況。在這種情況下，當 fast 指標到達 head 時，slow 指標也會同時指向 head。這導致後續操作出現錯誤：
將頭節點（dummy node）誤轉換為 element_t 型別，進而嘗試釋放錯誤的記憶體空間，最終引發 segmentation fault。
C99 6.3.2.3
A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned for the referenced type, the behavior is undefined.
在修正迴圈的判斷後即可順利執行程式。
- while (fast != head){
+ while (fast != head && fast->next != head){
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
element_t *element = list_entry(slow, element_t, list);
q_release_element(element);
q_ascend, q_descend
一開始沒有通過靜態程式分析，顯示變數 min_value 可以被宣告為 pointer to const：
Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:207:11: style: Variable 'min_value' can be declared as pointer to const [constVariablePointer]
char *max_value = curr->value;
起初我查找 C99 規格書想確認這個問題：
C99 6.7.3.5
If an attempt is made to modify an object defined with a const-qualified type through use of an lvalue with non-const-qualified type, the behavior is undefined.
在程式碼中， min_value 所指向的內容後續有可能被修改，不知道為什麼靜態分析過不了。
但後來我發現自己理解錯誤了。在宣告變數時：
const char *min_value = curr->value;
const 修飾的不是指標變數本身，而是指標所指向的內容。這表示我不能修改 min_value 所指向的記憶體位址中的字串，但仍然可以修改指標本身來指向不同的字串。
換句話說：
min_value = curr->value;
這樣的指派並不是在修改 min_value 原本指向的字串內容，而是讓指標指向新的位置，這種操作是被允許的。
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
if (head->next == head->prev)
return 1;
element_t *curr = list_entry(head->prev, element_t, list);
- char *min_value = curr->value;
+ const char *min_value = curr->value;
while (&curr->list != head) {
element_t *next = list_entry(curr->list.prev, element_t, list);
if (strcmp(curr->value, min_value) < 0) {
list_del(&curr->list);
q_release_element(curr);
} else {
min_value = curr->value;
}
curr = next;
}
return q_size(head);
}
q_swap
提交程式碼後重新看 List API 發現 list_move 可以直接取代我本來的寫法，修改後程式碼會更加精簡。
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *first = head->next;
while (first != head && first->next != head) {
- struct list_head *second = first->next;
- list_del(first);
- list_add(first, second);
+ list_move(first, first->next);
first = first->next;
}
}
q_delete_dup
原本我使用 list_for_each_entry_safe 來逐一走訪節點，但在提交程式碼時未能通過靜態分析：
Running static analysis...
queue.c:149:5: style: Label 'int' is not used. [unusedLabel]
if (&safe->list != head && !strcmp(safe->value, entry->value)) {
^
Fail to pass static analysis.
在 Facebook 社群發現其他同學也遇到相同問題。解決方案是將程式碼更新至較新版本。
然而，即使我已將程式碼更新至最新版本，靜態分析仍然報錯，目前尚未找出確切原因。
為了暫時解決這個問題，我將 list_for_each_entry_safe 改為使用 while 迴圈來通過靜態分析。不過，我希望撰寫作業時還是應該盡量以 List API 為主，待找出問題原因後再來進行修改。
todo
q_sort
一開始我嘗試參考〈 2025 年春季「Linux 核心設計」第 1 週測驗題 〉第三題的非遞迴版本 quick sort 來實作。然而，在測試過程中卻遇到了一些問題：
cmd> sort
ERROR: Not stable sort. The duplicate strings "gerbil" are not in the same order.
我發現 qtest.c 中包含了對排序穩定性的檢測機制。此外，考慮到在處理最多 100000 個節點的情況下：
int max_level = 2 * n;
struct list_head *begin[max_level];
begin 陣列的大小將達到 200000，這樣的記憶體配置相當龐大。
以上種種因素之下，我改成參考〈 你所不知道的 C 語言: linked list 和非連續記憶體 〉中遞迴版本的 merge sort 來完成本次作業。
q_merge
以上函式的 struct list_head *head 參數，大多都是指為了找到佇列整體而存在的 dummy node。不過，經過查看 qtest.c 的程式碼後發現，q_merge 函式中的 struct list_head *head 參數實際上是指向封裝在 queue_chain_t 結構體中的 list_head。
len = q_merge(&chain.head, descend);
在行前準備的部分，可以看到多個 queue_contex_t 是通過一個為首的 queue_chain_t 相互鏈結，形成了一個環狀雙向鏈結串列。兩種結構體都有封裝入 list_head。
q_merge 的目的就是透過逐一走訪 queue_contex_t，將每個 queue_contex_t 結構體中指向的環狀佇列合併成一個。
本來想說可以直接用在實作 q_sort 時已經寫好的 mergeTwoLists 函式來撰寫本題，但後來發現我忘記在使用快慢指標尋找中斷點之後，已經破壞了原本環狀佇列的結構。因此，mergeTwoLists 函式實際上並不適用於環狀佇列的情境。
基於這個原因，我另外實作了一個名為 mergeTwoLists_2 的函式，專門用於處理環狀佇列的合併操作。
到目前為止執行 make test 的結果是 95 / 100
執行make valgrind 未出現錯誤
研讀論文〈Dude, is my code constant time?〉
此篇論文一開始介紹到 timing attacks，這種資安攻擊可以透過測量加密實作的執行時間來推斷密鑰等等機密資訊。Timing attacks 跟許多其他攻擊方式相比，不需要太多與目標系統的接觸即可發動攻擊，且可以遠程操作，因此非常危險。評估實作是否真正達到 constant-time 執行並且不存在 timing leakage 是極具挑戰性的任務，即使是經過精心設計聲稱為 constant-time 的實作，後來也常被證明出存在漏洞。
再來作者繼續討論了檢測 variable-time code 的現有方法及其局限性。傳統方法需手動檢查 assembly code，耗時且須重複進行。現有工具如 ctgrind、Flow-tracker 和 ctverif 都需要硬體模型，但由於 CPU 的內部資訊是有限的，因此這項工作很困難。
基於上述限制，作者提出了 dudect：一個檢測程式碼是否達到 constant-time 執行的工具。此工具不依賴傳統的靜態分析方法，而是採用統計學的角度，通過對實際執行時間進行嚴謹的數據分析。
方法主要分為三個步驟：
- Measure execution time：重複測量某函式在兩種不同輸入測資下的執行時間，形成固定測資與隨機測資的兩個時間分布。
- Apply post-processing：對原始的時間測量數據進行處理，移除極端值。
- Apply statistical test：使用
Student's t-distribution檢驗，並且基於null assumption進行分析。
null assumption是指：無論輸入測資為何，程式的執行時間應該沒有顯著差異 ，即論文所述的 "the two timing distributions are equal"。
程式中的 simulation 方法
可以在 qtest.c 中發現，當 simulation 參數被設為 1 時，程式會執行 is_insert_tail_const、is_insert_head_const、is_remove_tail_const 或 is_remove_head_const 這四個函式之一，以檢測佇列的插入和移除操作是否為 constant。
在 deduct/fixture.c 中有定義以上四個函式會呼叫 test_const。
#define DUT_FUNC_IMPL(op) \
bool is_##op##_const(void) { return test_const(#op, DUT(op)); }
在 test_const 中，程式最多執行 TEST_TRIES 輪測試，並且分別使用固定測資與隨機測資進行測試。每輪測試中進行多次 doit 呼叫，直到收集到足夠的測量資料。
每次呼叫 doit 會執行 measure 函式，在 measure 函式中：
- 會跳過前
DROP_SIZE個索引位置 - 會跳過後
DROP_SIZE個索引位置 - 因此實際測量目標函式（即為佇列的插入或移除操作）的次數為
N_MEASURES-DROP_SIZE* 2 次 - 每次測量使用
cpucycles函式在操作前後記錄 CPU 週期計數器的值，計算時間差
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++)
再來利用 Welch's t-test 來統計檢驗兩種測資下的時間分布差異。
為什麼要跳過測量？
A : 還不知道
todo
在 do_it 的最後會基於計算出的 t 統計值判斷實作是否為 constant-time，以辨識潛在的 timing leakage。
說明 Student's t-distribution 及實作原理
Student's t-distribution 是一種連續機率分布。在這篇論文中，作者基於這個分布使用了 t-test 進行統計分析，以判斷程式碼是否為 constant。
參照 Student's t-test 裡面的 Assumptions，傳統的 Student t-test 需要滿足以下前提：
- 常態分布假設
The means of the two populations being compared should follow normal distributions - 相等變異數假設
If using Student's original definition of the t-test, the two populations being compared should have the same variance - 獨立性假設：
The data used to carry out the test should either be sampled independently from the two populations being compared or be fully paired
Welch's t-test 是 Student's t-test 的改進版本，主要的不同之處在於放寬了上述假設的第二點 —— 它是為了處理變異數不相等的情況而設計 ( is designed for unequal population variances )。這使得他更適用於這篇論文，因為不同輸入條件下的執行時間變異數通常不同。
關於 Welch's t-test 的實作可以參考 ttest.c 檔案，其中包含以下重要函式：
t_push
- 將新的測量值添加到兩種類別（固定/隨機）之一
- 計算新值與當前平均值之間的差異（delta）
- 更新平均值（mean)
- 更新平方差之和（m2）
t_compute
可以看到在公式中，
改進 percentile 的處理
查看原始碼中對於 prepare_percentiles 函式的註解，可以得知這個步驟的目的是要「set different thresholds for cropping measurements 」，這正是論文中 Step 2: Apply post-processing 所描述的 Cropping 方法，用來透過設定不同 thresholds 來移除極端的測量值。
在開始改進程式碼之前，先來看看原始碼是如何實作的：
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position < size);
return a_sorted[array_position];
}
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
首先，對測量出的執行時間以 ascending 方式排序，這是計算百分位數的必要前置步驟。
接著，針對每個索引值 i，程式會使用以下公式計算對應的百分位數：
1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES))
| i | which |
|---|---|
| 0 | 0.067 |
| 24 | 0.823 |
| 49 | 0.96875 |
| 74 | 0.994 |
| 99 | 0.999 |
可以看到呈現出一個從接近 0 到接近 1 的非線性分佈，特別集中在高百分位數區域（例如95%、99%、99.9%等）。
這樣處理的原因是，論文中有提到「 Typical timing distributions are positively skewed towards larger execution times. 」。
以下是 Positively Skewed Distribution 的圖示：
從圖中可見，大多數測量值集中在較短時間區間（圖左側較高部分），但同時存在少量極端的較長執行時間（圖右側尾巴部分）。論文解釋這種現象主要是由於測量過程中偶發的干擾因素，例如被作業系統中斷。
接下來程式會計算目標百分位數在排序好的測量時間中的具體數值作為thresholds。在 update_statistic 函式中，只會把不超過 threshold 的測量值加入分析，過濾掉了可能的極端值。
大致了解後，我在 dudect/fixture.c 中參考原始碼新增了以下三個函式：
static int cmp(const int64_t *a, const int64_t *b);
static int64_t percentile(int64_t *a_sorted, double which, size_t size);
static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles);
update_statistics 改寫成：如果執行時間大於等於 threshold 就會跳過該測量值，不將其加入統計分析。
- static void update_statistics(const int64_t *exec_times, uint8_t *classes)
+ static void update_statistics(const int64_t *exec_times,
+ uint8_t *classes,
+ const int64_t *percentiles)
{
- if (difference <= 0)
+ if (difference >= percentiles[i])
continue;
}
並且在 doit 函式中，呼叫 update_statistics 之前，先做 prepare_percentiles 處理。
static bool doit(int mode)
{
+ int64_t *percentiles = calloc(N_MEASURES, sizeof(int64_t));
- update_statistics(exec_times, classes);
+ prepare_percenrile(exec_times, percentiles);
+ update_statistics(exec_times, classes, percentiles);
}
完成後再次執行 make test 和 make valgrind 即可 100/100 通過，也有看到星之卡比。
透過 Massif 視覺化 simulation 過程中的記憶體使用量
參考 HenryChaing
Valgrind 可支援多種工具，其中分析記憶體使用狀況的工具叫做 Massif，可分析以下:
- Heap blocks：動態配置記憶體的區塊，也就是使用
malloc等函式所配置的記憶體空間。 - Heap administration blocks：用於管理 heap 記憶體的額外開銷區塊。
- Stack sizes：函式呼叫時所使用的堆疊空間大小。與 heap 不同，stack 的記憶體管理是自動的，當函式返回時就會自動釋放。
使用 massif 獲取程式在執行期間的記憶體使用狀況的 snapshot：
$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd
為了更容易理解 Massif 產生的資料，需要安裝一個視覺化的工具 Massif-visualizer：
$ sudo apt install massif-visualizer
使用 Massif-visualizer 來視覺化分析結果：
$ massif-visualizer massif.out.<pid>
藉由 massif 分析，我發現在實作 percentile 功能的部分存在問題。在 dudect/fixture.c 中的 doit 函式，我分配了記憶體給 percentiles 變數，但忘記在函式結束前釋放它。
透過新增以下修正：
+ free(percentiles);
並重新執行 valgrind 分析後，確認了此修正成功消除了程式中 doit 函式造成的記憶體洩漏。
從記憶體分析可以看出，test_const 和 test_malloc 在堆積使用上還是佔據較大比例。這是因為測試的設計：
- 在 simulation 模式中的函式呼叫關係：
test_const() -> doit() -> test_malloc()
- 在 harness.h 中的巨集定義：
#define malloc test_malloc
這個定義會將所有的 malloc 呼叫重新導向到 test_malloc。
每次對佇列進行操作（如 q_new、q_insert）時都需要配置記憶體，這些記憶體配置請求都會經由 test_malloc 處理，在測試過程中，大量重複的佇列操作導致累積了可觀的記憶體使用量。
在 qtest 提供新的命令 shuffle
Fisher–Yates shuffle 演算法
在 queue.c 和 queue.h 新增 q_shuffle 函式
void q_shuffle(struct list_head *head);
參考作業說明提供的演算法，交換 element_t 結構中的 value。
- 先用 q_size 取得 queue 的大小 len。
- 隨機從 0 ~ (len - 1) 中抽出一個數字 random，然後 old 將指向從前面數來第 random 個節點，new 會指向最後一個未被抽到的節點，將 old 和 new 指向的節點的值交換，再將 len - 1。
在 qtest.c 提供新的命令 shuffle 以及函式 do_shuffle
+ ADD_COMMAND(shuffle, "Shuffle nodes in queue", "");
統計的原理來分析實作
使用作業說明提供的測試程式進行實驗：
Expectation: 41666
Observation: {'1234': 41903, '1243': 41558, '1324': 41778, '1342': 41544, '1423': 41718, '1432': 41551, '2134': 41813, '2143': 41883, '2314': 41515, '2341': 41332, '2413': 41430, '2431': 41600, '3124': 41923, '3142': 41783, '3214': 41714, '3241': 41434, '3412': 41765, '3421': 41267, '4123': 41676, '4132': 41752, '4213': 41850, '4231': 41432, '4312': 42004, '4321': 41775}
chi square sum: 21.633898142370285
可以觀察到結果符合 uniform distribution。
整合網頁伺服器
select 系統呼叫在本程式的使用方式
在說明 select 以及 cmd_select 之前，有個重要的結構體要先認識：fd_set。
fd_set 是表示 file descriptors (fd) 集合的資料結構，它使用位元來表示每個 fd 的狀態。根據 <sys/select.h> 中定義的常數 FD_SETSIZE（通常為 1024），一個 fd_set 可以管理編號從 0 到 1023 的 fd。
fd_set 可以透過以下四種巨集來操作：
FD_ZERO(fd_set *set)：清除集合中所有的 fd（將所有位元設為 0），通常用於初始化。FD_SET(int fd, fd_set *set)：將指定的 fd 加入集合中（將對應位元設為 1）。FD_CLR(int fd, fd_set *set)：從集合中移除指定的 fd（將對應位元設為 0）。FD_ISSET(int fd, fd_set *set)：檢查指定的 fd 是否存在於集合中（測試對應位元是否為 1）。
select 函式主要是建立在 fd_set 型別的基礎上的：
int select(int nfds, fd_set *_Nullable restrict readfds,
fd_set *_Nullable restrict writefds,
fd_set *_Nullable restrict exceptfds,
struct timeval *_Nullable restrict timeout);
各個參數的功能如下：
readfds：用於監聽需要讀取的 fd。當selectreturn，只有已準備好可以讀取的 fd 會保留在集合中，其餘的都會被清除。writefds：用於監聽需要寫入的 fd。當selectreturn，只有已準備好可以寫入的 fd 會保留在集合中，其餘的都會被清除。exceptfds：用於監聽是否發生異常的 fd。當selectreturn，只有發生異常的 fd 會保留在集合中，其餘的都會被清除。nfds：指定要監聽的 fd 範圍。這個值會設為以上三種集合中最大的fd 值加 1。。timeout：用於控制select的等待時間。
總結來說，select 可以利用 bitwise operation 有效率的同時監聽多個 fd ，程式不必為每個連接或輸入來源建立獨立的執行緒。
cmd_select 是一個專門為命令處理而設計的函式，它在 select 系統呼叫的基礎上增加了命令處理的功能。
static int cmd_select(int nfds,
fd_set *readfds,
fd_set *writefds,
fd_set *exceptfds,
struct timeval *timeout)
參數與標準的 select 相同，但延伸了原本的功能：不只是檢查 fd 的狀態，還負責處理命令的輸入和執行。
在 lab0-c 中都是以 cmd_select(0, NULL, NULL, NULL, NULL) 的形式呼叫。會宣告本地的 fd_set 結構來管理要監聽的 fd，不需要另外傳入。
fd_set local_readset;
只會處理讀取，不會操作到 writefds 或 exceptfds 參數。如果沒有提供 readfds，就使用本地的 local_readset：
if (!readfds)
readfds = &local_readset;
當 Web server 存在時，會將其加入監聽。
if (web_fd != -1)
FD_SET(web_fd, readfds);
運用 CS:APP RIO 套件的原理和考量點
接下來介紹 console.c 中的全域變數 buf_stack。
static rio_t *buf_stack;
buf_stack 是指向 rio_t 結構體的指標。這個 rio_t 結構體，類似cmd_select 函式，也是一個經過擴充的設計。在了解這個延伸版本之前，先來看看它的原型：CS:APP RIO。
在 CS:APP 教材中，RIO（Robust I/O）的介紹之前，10.3 Reading and Writing Files 章節說明了 Short Counts 現象以及為什麼需要 RIO。
Short Counts 會在以下情況發生：
- 讀入時遇到EOF：當讀取到文件尾巴時，
read函式會返回小於請求的字節數。例如，如果檔案只剩 20 字節但要求讀取 50 字節，read會返回 20；再次讀取時會返回 0，表示已到達 EOF。 - 從 terminal 讀取 text lines：從 terminal 讀取時，每次
read呼叫會傳輸一行文本，回傳的 short counts 等於該文本行的長度。 - 讀寫 network sockets：內部 buffer 限制和網路的延遲可能導致
read和write函式回傳 short counts。
我本來以為 short counts 是一種錯誤情況需要特別處理。但正如 CS:APP 所說：
In practice, you will never encounter short counts when you read from disk files except on EOF, and you will never encounter short counts when you write to disk files. However, if you want to build robust (reliable) network applications such as Web servers, then you must deal with short counts by repeatedly calling read and write until all requested bytes have been transferred.
也就是說，雖然 short counts 本身不是錯誤，但它會造成實作上的挑戰，特別是在會用到網路的應用程式中。
舉例來說， web server 需要傳一個 8KB 的資料，簡單的呼叫一次 write 並假設所有資料都傳輸完成，這樣會有潛在的問題。可能由於 buffer 的限制，實際上只有 4KB 的資料傳送到 client。
參見 10.4 Robust Reading and Writing with the RIO Package 章節中，RIO套件的設計有兩個主要功能：
- Unbuffered input and output functions：會重複呼叫
read和write直到所有請求的 bytes 都被傳輸，目的在於解決上述的 short counts 狀況。 - Buffered input functions：lab0-c 實作的方式。使用 buffer 一次讀取大量資料，然後逐步從 buffer 提供資料給應用，避免頻繁的
read呼叫，提高 I/O 效率。
以下的討論都是針對 Buffered input functions 的情況
原始 RIO 套件中的 rio_t 結構定義：
typedef struct {
int rio_fd; /* descriptor for this internal buf */
int rio_cnt; /* unread bytes in internal buf */
char *rio_bufptr; /* next unread byte in internal buf */
char rio_buf[RIO_BUFSIZE]; /* internal buffer */
} rio_t;
console.c 裡面的 rio_t 結構定義：
typedef struct __rio {
int fd; /* File descriptor */
int count; /* Unread bytes in internal buffer */
char *bufptr; /* Next unread byte in internal buffer */
char buf[RIO_BUFSIZE]; /* Internal buffer */
struct __rio *prev; /* Next element in stack */
} rio_t;
可以看到相較於原始的 rio_t 多了 struct __rio *prev。這個 prev 指標透過將每個 rio_t 結構連結到前一個，從而實作了一個堆疊。先前提到的全域變數 buf_stack 會指向目前使用中的 buffer（堆疊的頂部），這讓程式可以同時處理多個輸入來源。
堆疊操作如下：
- 當推入新檔案時（透過
push_file函式），會建立一個新的 rio_t 結構，其 prev 指標指向目前堆疊的頂部，然後 buf_stack 更新為指向這個新結構。 - 當檔案處理完成時（透過
pop_file函式），堆疊最上面的 rio_t 結構被移除並釋放，buf_stack 重設為堆疊中的前一個元素。
因此程式在處理完新檔案後，可以返回處理原先的檔案，實作了一種 LIFO 的巢狀檔案處理方式。
搭配圖片服用會比較清楚：
以下是呼叫兩次 push_file 的結果（先不管 buffer 內容）
舉例來說，若使用者先輸入 source main.cmd 命令，接著在 main.cmd 執行過程中遇到 source sub.cmd 命令，則會形成一個長度為 3 的堆疊（標準輸入、main.cmd 和 sub.cmd）。
此時，buf_stack 指向堆疊頂部的 sub.cmd 對應的 rio_t 結構。當程式需要讀取命令時，它會從 buf_stack 指向的 buffer 獲取資料。如果 buffer 為空，程式會呼叫 read 從 sub.cmd 一次性讀取多個字節（最多 RIO_BUFSIZE）到 buffer，然後逐字節處理這些資料，大幅減少系統呼叫次數。
程式會先處理堆疊頂部的檔案，因此優先執行 sub.cmd 中的所有命令。當 sub.cmd 執行完畢時，程式會呼叫 pop_file 函式，釋放目前 buf_stack 指向的 rio_t 結構，並將 buf_stack 重新指向堆疊中的前一個元素（即為 main.cmd 的 rio_t）。
此時堆疊長度減為 2，程式會繼續從 main.cmd 的 buffer 讀取並執行 source sub.cmd 之後的命令。由於每個輸入來源都有自己獨立的 buffer 和追蹤的變數（即為 rio_t 結構體中的 count 和 bufptr），因此不需重新讀取或重置文件位置。
到這裡回歸題目：運用 CS:APP RIO 套件的原理和考量點是什麼？
我覺得主要有三點：
- 使用內部 buffer 一次讀取較大塊資料，減少系統呼叫次數，提高效率。這個方法也很適合處理以行為單位的輸入，如同本次作業的命令。
- 延伸原始 rio_t 結構，增加 prev 指標，讓程式可以執行巢狀命令處理（如 source 命令）。
- 結合
select系統呼叫與 buffer，實作出單一執行緒同時監聽並高效處理多個輸入來源的功能。
分析 console.c 的實作
qtest.c 會呼叫 console.c 中的run_console，這個函式的行為主要是由 has_infile 以及 use_linenoise 這兩個變數來決定。
- has_infile 用來判斷目前的輸入模式
- use_linenoise 用來判斷目前的輸入處理方式
流程如下：
- 如果是標準輸入模式（
has_infile == false）- 如果
use_linenoise == true：使用 linenoise 處理標準輸入- 如果遇到 source 命令，檔案被推入堆疊，此時
buf_stack->fd != STDIN_FILENO，暫時使用cmd_select處理檔案輸入。 - 直到堆疊裡面的所有檔案處理完畢，然後回到使用 linenoise 處理標準輸入。
- 如果遇到 source 命令，檔案被推入堆疊，此時
- 如果
use_linenoise == false，即為執行了 web 命令後：使用cmd_select處理所有輸入。
- 如果
- 如果是檔案輸入模式（
has_infile == true）：直接使用cmd_select處理檔案輸入。
3/22 更新
以下問題看到有同學發 pr 修改完成了
我有順便把 lab0-c 的作業說明文件同步更新
我有個疑惑的地方在於 cmd_select 裡面有段程式碼：
/* If web not ready listen */
if (web_fd != -1)
FD_SET(web_fd, readfds);
我以為是如果 web server 已準備好，就會透過 FD_SET 把 web_fd 加入集合監聽，但是註解是說明「If web not ready listen」，不知道我是否有理解錯誤的部分。
Linux 核心的鏈結串列排序
研讀 lib/list_sort.c 以及論文
因為時間有限，又不想單單只看前人們整理好的論文重點，於是跟修課夥伴決定先一人啃一篇。
我負責研讀 〈 The cost distribution of queue-mergesort, optimal mergesorts, and power-of-two rules 〉，詳見 研讀 list_sort + 論文，當中藍色的部分是研讀心得，以下也會把部分心得放在這邊繼續討論。
- stable sorting && how does list_sort work
From a practical viewpoint, QM is easily implemented on linked list, its
code being simpler than those of TDM and BUM. Also the size of the input need not be known in advance and it can be implemented in either a top-down or a bottom-up manner, making QM an attractive alternative to TDM and BUM. The price we pay is stability: QM is not stable for equal keys.
傳統的 QM 有個主要的問題是他的演算法不符合 stable sorting，因為他的行為會是一直把合併排序好的鏈結串列放到佇列的尾巴，直到佇列中剩下一個元素。
於是想要探討 list sort 原始碼，說明 list sort 用什麼方式補足了這個缺陷。
count = 0 -> count = 1
count = 1 -> count = 2
count = 2 -> count = 3
呼叫 merge(priv, cmp, b, a)
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
可以看到當待合併的兩個值相同時，總是選擇第一個參數，即為剛剛傳入的 b = a->prev，所以合併時會保持元素的相對順序。
此時 pending 中是已經排序好的 A -> A'，新增元素 A'' 到 pending 的頭。
此時 pending 包含兩個元素：一個大小為 1 的 A'' 和一個大小為 2 的 A -> A'。
list 為空，代表已經沒有要繼續插入的節點。將所有 pending 中的鏈結串列從長度最小到最大逐個合併。
/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
struct list_head *next = pending->prev;
if (!next)
break;
list = merge(priv, cmp, pending, list);
pending = next;
}
- 如果原始的 pending 只有一個子元素（排序好的鏈結串列），那麼 list 會是這個子元素，而 pending 會是 NULL
- 如果原始的 pending 有兩個子元素，那麼 list 會是第一個子元素，pending 會是第二個子元素
- 如果原始的 pending 有多個子元素，那麼除了最後一個子元素外，其他所有子元素都會被合併到 list 中，而 pending 會指向最後一個子元素
新的元素從 pending 的頭插入，以及這部分的從 pending 的頭合併，都是為了確保 list_sort 總是選擇長度最小的兩個子元素合併，這會形成一種平衡，使得最終剩下的兩個子元素的大小盡可能接近。
這點在 研讀 list_sort + 論文 當中也有提及到
呼叫 merge_final(priv, cmp, head, pending, list)，建構雙向鏈結串列結構。
- insight of Lemma 1
雖然 QM 的實作是 bottom-up 的，但行為模式可以用 top-down 的 balanced power-of-2 rule 分割方式來詮釋。
我自己的理解是：
QM 用一種類似 top-down 的想法（？）來實作 bottom-up，他保留了 bottom-up 的好處與特性，比如說實作上只需簡單的佇列操作和迴圈，以及單純合併對 cache 更加友善等等，但他同時在效能上擁有 worst case optimal 以及 asymptotically optimal，不需要透過像 TDM 的切割步驟，QM 就擁有了類似於 TDM 的平衡特性。3/22 讀書會討論的時候，在這個部分聯想到林本然負責研讀的論文：
〈 Bottom-up Mergesort: A Detailed Analysis 〉
當中有提到遞迴版本的 bottom-up，我們認為他也是用 top-down 想法詮釋 bottom-up 的實例之一。
還不確定這段話是否正確，論文中還有許多可以挖掘的地方。
-
why list_sort
這個問題的答案我想可以先用 why QM 來回答：- worst case optimal
論文證明，根據 Hammersley 和 Grimmett 的研究結果，任何使用 two-way linear 合併的 mergesort，如果切割結果在每個遞迴階段都滿足
- variance asymptotically optimal && asymptotic normality，且不像 TDM 有週期性振盪，更加穩定可預測。
- 不需要事先知道輸入大小，且實作上用佇列比 TDM、BUM 更加簡潔。
- 使用 balanced power-of-2 rule，比傳統的 BUM 更平衡。
- 雖然平均的比較次數略高於 TDM，但仍優於 BUM。
- 帶有 BUM 以及 TDM 各自的優點。
list_sort 除了保留 QM 的優點之餘，還解決了 QM 不 stable 的問題。
- worst case optimal
比較自己實作的 merge sort 和 list_sort 之間的效能落差
todo
lab0-c Pull Request
在把 list_sort 功能實作到目前程式碼的過程中，發現 queue.h 中有一些文法錯誤，提交 pr 後目前已經 merge 了。這是我第一次發 pr 到這種開源的專案，雖然真的是超小超小的問題，不過還是期許自己繼續加油，補足不足之處，才能發現並改進更重要的缺失。
教材閱讀
〈 你所不知道的 C 語言：指標篇 〉
在 C99 [6.2.5] Types 的部分讀到要區分 char [] 和 char *，而後又在 derived declarator types 的說明看到
array function pointer 其實是一樣的，重點都在位址
感覺到矛盾，於是嘗試釐清我尚未理解的基本概念。
如果從 derived declarator types 開始為例子：
int number; // fundamental type
- array
int numbers[10]; // array - derived from int
- 當陣列傳遞給函式時，傳遞的是起始位址
- 陣列名 numbers 代表陣列第一個元素的位址
- function
int add(int, int); // function - derived from int
- 當傳遞函式作為參數時，傳遞的是函式的位址
- 函式名 add 代表函式在記憶體中的位址
- pointer
int *ptr; // pointer - derived from int
- 指標 ptr 直接儲存位址值
這就是為什麼它們被歸類為 derived declarator types， 因為它們都是透過位址的概念來運作。
那為什麼要區分 char [] 和 char *？
參考該教材中 Pointers vs. Arrays 的部分，陣列名稱在以下兩種狀況下會被轉為「一個指向陣列的第一個元素的指標」：
- parameter of function，如
func(char x[])可變更為指標的形式func(char *x) - 在 expression 內使用時
但他們還是存在著差異：
- 存取方式
char arr[4] = {'a', 'b', 'c', 'd'};
char *ptr = arr;
- 存取
arr[2]的步驟：取得 arr 的起始位址 -> 加上 offset 2 - 存取
ptr[2]的步驟：載入 ptr 的位址 -> 取得 ptr 儲存的值，也就是 arr 的起始位址 -> 加上 offset 2
- 記憶體配置
char p[] = "hello"：字串本身在 static storage 並且會被複製到 stack 所分配的陣列空間char *p = "hello"：stack 配置 p 的位址，p 指向 static storage 中的字串- 因此針對字串的操作，像是修改內容或是取得大小也會有不同結果
〈 你所不知道的 C 語言: 浮點數運算 〉
在讀到 Uneven density of the floating point numbers 時，浮點數在數線上不均勻的分佈看似是缺陷，但其實是經過深思熟慮的設計選擇。
在 32 bit 的記憶體空間中，可以表示 2^32 個不同的整數，不過在表示實數時會有侷限。浮點數透過讓指數來調整小數點的位置，使得同樣的 32 bit 空間也可以表示從極小到極大的廣泛數值範圍。
指數的設計雖然犧牲了數值的準確度來換取了更大的表示範圍，但是較大的數值即使有較大的絕對誤差，他們的相對誤差仍然維持在可接受的範圍內。
我才明白為什麼浮點數會叫做「浮」點數。
待整理
Linux hash table 設計的思維是建立在 hash function 不太碰撞的前提之下？
C 語言標準明確允許實作自行決定在以下兩種狀況下是否是陷阱表示法：
（ 允許「實作」自行決定？？？ ）
在〈 2025 年 Linux 核心設計課程作業 —— lab0 (A) 〉中
你的程式碼將透過 1,000,000 個以上節點的佇列進行測試。
但是在 qtest.c 中
#define MAX_NODES 100000
