---
# System prepended metadata

title: 2025q1 Homework1 (lab0)

---

# 2025q1 Homework1 (lab0)
contributed by < [`Urbaner3`](https://github.com/Urbaner3/lab0-c) >

### Reviewed by `liangchingyun`
> 在內文中提及程式碼時，應使用反引號，例如 `q_reverseK(head, 2)`
>> 好，函式要，但僅名稱如 q_swap 我就不用了，方便閱讀，否則太多瑩光標註。 By `Urbaner3`

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            13th Gen Intel(R) Core(TM) i5-1340P
    CPU family:          6
    Model:               186
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            2
    CPU max MHz:         4600.0000
    CPU min MHz:         400.0000
    BogoMIPS:            4377.60
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
                         a cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss 
                         ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art
                          arch_perfmon pebs bts rep_good nopl xtopology nonstop_
                         tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes6
                         4 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xt
                         pr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_
                         timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefet
                         ch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_enhanced t
                         pr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adj
                         ust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap cl
                         flushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 x
                         saves split_lock_detect avx_vnni dtherm ida arat pln pt
                         s hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req hfi
                          vnmi umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid
                          movdiri movdir64b fsrm md_clear serialize arch_lbr ibt
                          flush_l1d arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   448 KiB (12 instances)
  L1i:                   640 KiB (12 instances)
  L2:                    9 MiB (6 instances)
  L3:                    12 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-15
Vulnerabilities:         
  Gather data sampling:  Not affected
  Itlb multihit:         Not affected
  L1tf:                  Not affected
  Mds:                   Not affected
  Meltdown:              Not affected
  Mmio stale data:       Not affected
  Retbleed:              Not affected
  Spec rstack overflow:  Not affected
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer
                          sanitization
  Spectre v2:            Mitigation; Enhanced / Automatic IBRS; IBPB conditional
                         ; RSB filling; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
  Srbds:                 Not affected
  Tsx async abort:       Not affected
$ 

```

## Reviews

## 新聞



## 準備工具與材料

[^Ref]
[^Ref]:[mdref](https://hackmd.io/Z-vcRTCjQdKqu4UAyswd5g?view) 主題完整

[yy](https://hackmd.io/@yy214123/linux2025-homework1) 我和他一樣重頭砍掉重練。
<`chennship`> [harness](https://hackmd.io/@chensheep/linux2025-homework1) 提到要解決記憶體問題，第一次就注意到不簡單。跟著做。

[共筆規範](https://hackmd.io/@sysprog/linux2025-sample-lab0) 太誇張了，竟然寫的這麼清楚，想想覺得壓力很大，不努力不行。參考 < `BigMickey` > 的筆記，像我以前一樣，方格接近流水帳，用 commit 來省略比較簡潔，共筆需要的是溝通，流水帳最多是給助教看吧。我決定把流水帳的筆記稱作童話故事，會有完整的細節，應該很亂。這裡是現實。


#### 參考材料

這裡簡單列一些重要材料，<指標篇>、 <linked_list 篇>。附錄 container_of 篇。前置處理器篇，告訴我 `header` 檔案的歷史。我8日凌晨還看了很多影片，記在日曆上面。 為了瞭解 <`yy`> 他為什麼會去思考更改 `harness` 檔案， 我看了...
[動態配置記憶體1](https://youtu.be/_8-ht2AKyH4?si=1n6beVN_4p3B5ERu) `mycodeschool` [記憶體分區](https://youtu.be/2htbIR2QpaM?si=dd7AhYps3RwuZzHN) `Ryan Baker` 兩部影片說明動態記憶體配置的形態，概念，這讓我想到<記憶體管理...特性篇>，還有<每位程式開發者都該有的記憶體配置> 和在一起看，[共筆規範](https://hackmd.io/@sysprog/linux2025-sample-lab0)、<`chensheep`>、<yy> 他們刻意處理 q_free 的部分，記憶體對齊錯誤的問題，就有了線索，我決定先做到 `make check` 有關的運算就好不然我記不住了，記憶體不足。會記錯和迷失。

```shell
qcheck: qtest
	./$< -v 3 -f traces/trace-eg.cmd

qtest: $(OBJS)
	$(VECHO) "  LD\t$@\n" 
	$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
```
           
因為我無法預測 Makefile 自動化編排的機制，所以我用 GPT 去執行翻譯，前後線索我整理不起來，很多猜測人心的桌遊，比如風聲，我不擅長。結果是：
```bash
# 建立編譯暫存目錄
mkdir -p .dudect

# 編譯各個原始檔案
gcc -o queue.o -Wall -Wextra -Werror -std=gnu11 -Og -ggdb -fsanitize=address -fno-omit-frame-pointer -fno-common -c -MMD -MF .queue.o.d queue.c
gcc -o harness.o -Wall -Wextra -Werror -std=gnu11 -Og -ggdb -fsanitize=address -fno-omit-frame-pointer -fno-common -c -MMD -MF .harness.o.d harness.c
gcc -o console.o -Wall -Wextra -Werror -std=gnu11 -Og -ggdb -fsanitize=address -fno-omit-frame-pointer -fno-common -c -MMD -MF .console.o.d console.c
# （其他檔案依此類推）

# 連結所有目的檔，產生可執行檔 qtest
gcc -fsanitize=address -o qtest queue.o harness.o console.o -lm

# 執行測試程式
./qtest -v 3 -f traces/trace-eg.cmd
```
           
### 連結列檔案目錄
配合 Leetcode [assist](https://hackmd.io/48Jiy_x8TziHexUx_uXiHQ) 做鏈結佇列的相關運算，把[過去記錄](https://hackmd.io/_sS3BitpSMuUPvLRAwhlGg)備著繼續進行。想到還有[藍圖](https://hackmd.io/@Urbaner/blueprint) 和 [重做 lab0 專案](https://hackmd.io/@sysprog/Syc7ROemA)低能參考。
           (https://hackmd.io/@sysprog/linux2024-projects#%E9%87%8D%E5%81%9A-lab0-%E4%B8%A6%E5%BD%99%E6%95%B4%E5%AD%B8%E5%93%A1%E6%88%90%E6%9E%9C)7份。
           
[hw1作業區](https://hackmd.io/@sysprog/linux2025-homework1)，因為我沒有上課，所以課堂上的問題答不出來，雖然是可以問同學，但我想想，沒意義沒營養。直接做自己的作業區就好了，上面的藍圖，就已經是這樣子的頁面了。所以多兩個連結： hw3作業：           [2025 q1 kxo 核心模組開發記錄](/qpBLI1ytTDyr1OLHUe0qrQ); hw4作業：[2025q1 Homework4 (quiz3+4)](/lNkav1UhRWeM8q3l6-biMA)
           
**接下來要講的很重要，是整份專案當中最容易出錯，需要耐心多讀幾次的。** 就是作業解說二 <qtest 命令直譯器的實作> 這一代的說明引用很多文獻，沒有完全搞懂，強行運作，會很痛苦，建議找懂的人，放慢腳步，不然會因為步驟跳躍，產生斷片感。
    
實測 <`chensheep`> 的記憶體檢測方法，並按照老師說的，修改 harness.c ，但注意 184行的名稱有些出入。 block_ele。 還有 alloc 被獨立出來了。成為一個函式的原型。

我發現教材有些出入。去年 3月 17日有個 22年修課的同學，把 malloc 和 calloc 共用的部分整合成一個 enum 物件叫 alloc 概念還沒抓到，但語法邏輯可以記住。
他又創造了函式 alloc 才導致我跟你的誤會，另外教材有寫 block_ele_t ，應修正為 block_element_t，事實上 alloc 是對的，但教材可以適當調整改成叫學生觀察 alloc 函式中的實作，甚至搜尋 *alloc ，當然理論上學生應有能力判斷， 因為 malloc 的 return 就是 alloc 函式的結果。
但寫法直覺就是好路標的功用，就是針對冗長的說法去改進。
請容我修改教材。

## 修改教材：
### 2025 年 Linux 核心設計課程作業 —— lab0 (B)
    
![image](https://hackmd.io/_uploads/SkwG_HZna.png)

`test_malloc` 函式實作如下:
"">>>>>>"從這裡開始
>根據 commit f087e77 <`komark06`> 利用 alloc 相關物件宣告改變了 `test_malloc` 函式的實作。後者即為 `alloc` 函式的合成，其實作為：

```c
void *test_malloc(size_t size)
{
    return alloc(TEST_MALLOC, size);
}
```
其中，`alloc` 函式實作如下：    
```c
static void *alloc(alloc_t alloc_type, size_t size)
{
    if (noallocate_mode) {
        char *msg_alloc_forbidden[] = {
            "Calls to malloc are disallowed",
            "Calls to calloc are disallowed",
        };
        report_event(MSG_FATAL, "%s", msg_alloc_forbidden[alloc_type]);
        return NULL;
    }

    if (fail_allocation()) {
        char *msg_alloc_failure[] = {
            "Malloc returning NULL",
            "Calloc returning NULL",
        };
        report_event(MSG_WARN, "%s", msg_alloc_failure[alloc_type]);
        return NULL;
    }

    block_element_t *new_block =
        malloc(size + sizeof(block_element_t) + sizeof(size_t));
    ...
```
>這是24年以前的舊版本。特別留意 `block_ele_t` 應為 `block_element_t`。commit ef0b584 <`Jim Huang`> 把名字改了，注意教材對應新版程式碼的 `block_element_t` type 型別。另外搜索 'linux kernel `block_element_t`' ，會發現原始文件[版本](https://hackmd.io/@0xff07/SJnc7dtSN?type=view#shell-%E5%AF%A6%E4%BD%9C)，出自一位 <`0xff07`> 學長，很多細節值得一看。另外，[當年設定](https://github.com/0xff07/lab0-c) ` 那時候的 ELE 就是今天的 element， 在 queue.h 理頭。
    
"">>>>>>"到這裡
```c
void *test_malloc(size_t size)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to malloc disallowed");
        return NULL;
    }
    if (fail_allocation()) {
        report_event(MSG_WARN, "Malloc returning NULL");
        return NULL;
    }
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    ...
 ```   
這技巧體現於程式碼的 `malloc(size + sizeof(block_ele_t) + sizeof(size_t))` 當中。除了 `sizeof(block_ele_t)` 與 `size`， 還多了 `sizeof(size_t)` 的空間。這是因為使用者實際可使用的記憶體，前後被兩個 `size_t` 整數包著，裡面各自紀錄著兩個 Magic Number，作為驗證這塊記憶體是否是由 `test_malloc` 分配的依據，以及作為記憶體是否有產生越界等不佳使用的依據。
`test_malloc` 配置的空間，示意如下圖:
![image](https://hackmd.io/_uploads/rJNmuHb2T.png)
:::info
gcc 的擴充功能 "Arrays of Length Zero" 在 Linux 核心大量使用，可參照中文解說 [C Struct Hack - Structure with variable length array](https://frankchang0125.blogspot.com/2013/01/c-struct-hack-structure-with-variable.html)
:::
    
>注意，講師 jserv 有為了凸顯項目符號 1. 讓段落縮排，我只是呈現內容，略去前者的操作。

### 整理架構

竟然有名詞的改動，而且是老師的行動，那值得深究。用`grep -r element` 搜尋檔案，找一些重要的鏈結串列，都是雙向侵入式鏈結串列。
>queue.h:} element_t; 
>console.h:} cmd_element_t;
>console.h:} param_element_t;
>harness.c:} block_element_t;

為了測試並了解教材的操作，我去抓取[原版程式](https://github.com/0xff07/lab0-c)

search "gdb call stack command",[page](https://cgi.cse.unsw.edu.au/~learn/debugging/modules/gdb_call_stack/) with 2 examples call_stack.c and corrupted_linked_list.c 
>call stack using the where, up, down and frame commands.

經過整理教材後，我知道**危險**之處在哪理了。這邊有些段落從[原始文章](https://hackmd.io/@0xff07/SJnc7dtSN?type=view#shell-%E5%AF%A6%E4%BD%9C)引用，細看可以發現，順序有點簡化，前後有些不對應。
>`gdb ./qtest`
>cmd> run -> new -> ih hello
ctrl - C sends singal, 會得到畫面：

```shell
cmd> ^C
Program received signal SIGINT, Interrupt.
0x00007ffff7d1b59d in __GI___select (nfds=nfds@entry=1, readfds=readfds@entry=0x7fffffffd410, writefds=writefds@entry=0x0, exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x0) at ../sysdeps/unix/sysv/linux/select.c:69
69	../sysdeps/unix/sysv/linux/select.c: No such file or directory.
(gdb) bt
#0  0x00007ffff7d1b59d in __GI___select (nfds=nfds@entry=1, 
    readfds=readfds@entry=0x7fffffffd410, writefds=writefds@entry=0x0, 
    exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x0)
    at ../sysdeps/unix/sysv/linux/select.c:69
#1  0x000055555555973a in cmd_select (nfds=1, nfds@entry=0, 
    readfds=0x7fffffffd410, readfds@entry=0x0, writefds=writefds@entry=0x0, 
    exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x0) at console.c:598
#2  0x0000555555559855 in run_console (infile_name=infile_name@entry=0x0)
    at console.c:630
#3  0x0000555555557fa2 in main (argc=1, argv=0x7fffffffd928) at qtest.c:770

```
注意到 `parse_args` 這個函式沒有出現，用 `grep -r parse` 尋找會找到 `console.c:static char **parse_args` 再想想為什麼他走了不同的分支。 我實測我[2022年的程式]()發現，發出 signal 時會 free queue gdb 不會暫停。這表示自動程式控制，有被修改到了。注意差別思考可以到這一段的重要課題。也知道作業說明是舊版畫面，還是新版好吧，後面多了 `at file:line` 方便找上下文。
    
## Core dump and analysis

```shell
(base) urbaner@urbaner-wtumagic:~/linux2025/chensheep/lab0-c$ coredumpctl gdb
           PID: 16895 (qtest)
           UID: 1000 (urbaner)
           GID: 1000 (urbaner)
        Signal: 6 (ABRT)
     Timestamp: Wed 2025-03-12 02:39:12 CST (14min ago)
  Command Line: ./qtest
    Executable: /home/urbaner/linux2025/chensheep/lab0-c/qtest
 Control Group: /user.slice/user-1000.slice/user@1000.service/app.slice/app-org.gnome.Terminal.slice/vte-spawn-3c366399-18a2-4d95-a120-114c4600b160.scope
          Unit: user@1000.service
     User Unit: vte-spawn-3c366399-18a2-4d95-a120-114c4600b160.scope
         Slice: user-1000.slice
     Owner UID: 1000 (urbaner)
       Boot ID: 1cd399f77952431bbf9a78b99fbd120d
    Machine ID: 10b971ac1a304176906b1f6a23827476
      Hostname: urbaner-wtumagic
       Storage: /var/lib/systemd/coredump/core.qtest.1000.1cd399f77952431bbf9a78b99fbd120d.16895.1741718352000000.zst (present)
     Disk Size: 24.8K
       Message: Process 16895 (qtest) of user 1000 dumped core.
                
                Found module /home/urbaner/linux2025/chensheep/lab0-c/qtest with build-id: 97ab618d8e3200dc2a71b25453f3b717a6104447
                Found module linux-vdso.so.1 with build-id: 9fd856095d9a973579d1f96e0eb3d9030c15f0f2
                Found module ld-linux-x86-64.so.2 with build-id: e4de036b19e4768e7591b596c4be9f9015f2d28a
                Found module libc.so.6 with build-id: cd410b710f0f094c6832edd95931006d883af48e
                Found module libm.so.6 with build-id: 7d8778fca8ea4621b268cc03662855d0cd983439
                Stack trace of thread 16895:
                #0  0x000073c3e6a969fc __pthread_kill_implementation (libc.so.6 + 0x969fc)
                #1  0x000073c3e6a42476 __GI_raise (libc.so.6 + 0x42476)
                #2  0x000073c3e6a287f3 __GI_abort (libc.so.6 + 0x287f3)
                #3  0x00005ef732f0d762 n/a (/home/urbaner/linux2025/chensheep/lab0-c/qtest + 0x3762)

GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1
Copyright (C) 2022 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from /home/urbaner/linux2025/chensheep/lab0-c/qtest...
[New LWP 16895]
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Core was generated by `./qtest'.
Program terminated with signal SIGABRT, Aborted.
#0  __pthread_kill_implementation (no_tid=0, signo=6, threadid=127285227788096)
    at ./nptl/pthread_kill.c:44
44	./nptl/pthread_kill.c: No such file or directory.
(gdb) bt
#0  __pthread_kill_implementation (no_tid=0, signo=6, threadid=127285227788096)
    at ./nptl/pthread_kill.c:44
#1  __pthread_kill_internal (signo=6, threadid=127285227788096)
    at ./nptl/pthread_kill.c:78
#2  __GI___pthread_kill (threadid=127285227788096, signo=signo@entry=6)
    at ./nptl/pthread_kill.c:89
#3  0x000073c3e6a42476 in __GI_raise (sig=sig@entry=6)
    at ../sysdeps/posix/raise.c:26
#4  0x000073c3e6a287f3 in __GI_abort () at ./stdlib/abort.c:79
#5  0x00005ef732f0d762 in sigsegv_handler (sig=<optimized out>) at qtest.c:1118
#6  <signal handler called>
#7  0x00005ef732f0ee72 in queue_insert (pos=pos@entry=POS_HEAD, 
    argc=<optimized out>, argv=<optimized out>) at qtest.c:240
#8  0x00005ef732f0f02a in do_ih (argc=<optimized out>, argv=<optimized out>)
    at qtest.c:282
#9  0x00005ef732f108fe in interpret_cmda (argc=argc@entry=2, 
    argv=argv@entry=0x5ef7339e9110) at console.c:214
#10 0x00005ef732f10c8a in interpret_cmd (
    cmdline=cmdline@entry=0x5ef7339e8c50 "ih aksdjf") at console.c:234
#11 0x00005ef732f1178e in run_console (infile_name=infile_name@entry=0x0)
    at console.c:669
#12 0x00005ef732f0faa3 in main (argc=1, argv=<optimized out>) at qtest.c:1444

```

其實這個錯誤檔案，反而幫助我了解最初狀態下，程式的運行機制，這是 chensheep 的 master 分支，他把所有開發都放到另一個開發分支，不知道什麼時候他會並進來，或是 rebase 。這很像加盟和併購，我是指 git branch 兩種合併的方式。
    
[24年惟欣lab0](https://hackmd.io/@weihsinyeh/SJUVTnEn6) 用自己寫法定義一些自己方便的說法，讓自己熟悉了解記憶體的建立和刪去。昨天測試的也是好例子。
    
## Valgrind 嘗試修正 leak
理解修正的狀況之後，才有辦法修正 direct memory leak。
```shell
(base) urbaner@urbaner-wtumagic:~/linux2025/call_stack$ valgrind -q --leak-check=full ./corrupted_linked_list 
0->1->2->3->4->5->6->X
==3603== 112 (16 direct, 96 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==3603==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3603==    by 0x1091EE: create_node (corrupted_linked_list.c:25)
==3603==    by 0x109263: create_list (corrupted_linked_list.c:36)
==3603==    by 0x1091BE: main (corrupted_linked_list.c:18)
==3603== 
(base) urbaner@urbaner-wtumagic:~/linux2025/call_stack$ vi corrupted_linked_list.c
(base) urbaner@urbaner-wtumagic:~/linux2025/call_stack$ gcc -g -o corrupted_linked_list corrupted_linked_list.c
(base) urbaner@urbaner-wtumagic:~/linux2025/call_stack$ valgrind -q --leak-check=full ./corrupted_linked_list 
0->1->2->X
==3649== 48 (16 direct, 32 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==3649==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3649==    by 0x1091EE: create_node (corrupted_linked_list.c:25)
==3649==    by 0x109263: create_list (corrupted_linked_list.c:36)
==3649==    by 0x1091BE: main (corrupted_linked_list.c:18)
==3649== 

(base) urbaner@urbaner-wtumagic:~/linux2025/call_stack$ valgrind -q --leak-check=full ./corrupted_linked_list 
0->X
==7094== 16 bytes in 1 blocks are definitely lost in loss record 1 of 1
==7094==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==7094==    by 0x1091EE: create_node (corrupted_linked_list.c:25)
==7094==    by 0x109263: create_list (corrupted_linked_list.c:36)
==7094==    by 0x1091BE: main (corrupted_linked_list.c:18)
==7094== 
    
```
其實認真檢查，只要 option failure =30 不會有 memory leak，quit 也會 free 記憶體。但可計算時間，來估計記憶體使用情形。
    
    
## 補充 qtest 命令直譯器介面
互動介面，如 qtest 利用 cmd_element_t 的鏈結串列記錄輸入的命令，然後交給 interpret_* 系列檔案執行。依照我軟韌體使用者介面工作經驗，通常會有的迴圈重複執行直到，quit 或是 break 結束迴圈。
```shell
(base) urbaner@urbaner-wtumagic:~/linux2025/lab0-c$ ./qtest -v
./qtest: option requires an argument -- 'v'
Unknown option '?'
Usage: ./qtest [-h] [-f IFILE][-v VLEVEL][-l LFILE]
	-h         Print this information
	-f IFILE   Read commands from IFILE
	-v VLEVEL  Set verbosity level
	-l LFILE   Echo results to LFILE
```
基本上仔細看，三個表單結構，類似，操作界面也類似或是對稱，但迴圈是 for 或是 for_each_node_safe。
queue_element_t ，另外兩個鏈結串列是 cmd_element_t 和 para_meter，一起交給 console 和 report 分別記錄命令劇本，和回傳錯誤訊息。直覺來講，console 很像變數型別，專門產生 cmd_element_t 成為一個串列； report 利用一系列的 printf 透過檔案，輸出訊息給 qtest 的交互輸入。
簡單的結構，corrupted_linked_list 中是 create_list 中的 while 為名，實為 for 迴圈架構的迴圈。
    [callgrind](https://hackmd.io/@0xff07/ncku-sysprog-assignments/https%3A%2F%2Fhackmd.io%2F%400xff07%2Fr1UtHAPKg) 工具，搭配 kcachegrind，可以看出 call graph，並知道 report 就是設定細節的 printf。
    
## 釋放記憶體 corrupted_linked_list 練習
    
call stack command 的練習檔案中，發現 corrupted_linked_list.c 沒有釋放記憶體。嘗試實作。猜測需要 free curr, 和 next 因為 16, 48, 112 正比於 1, 2, 7 就是節點數量，只要加入 remove 的函式就可以了。

```cpp=
void print_list(struct node *list){
    struct node *curr = list;
    struct node *to_del;

    while (curr != NULL) {
        printf("%d->", curr->data);
        to_del = curr;
        curr = curr->next;
        // remove_head(to_del);
        free(to_del);
    }
    printf("X\n");
}
````
注意迴圈的用法，配合迴圈用上，第3,7行的指標，第10行的 free 函式。記憶體缺失就消失了。但 qtest.c 有四個鏈結串列和兩個迴圈，必須每個迴圈都處理，或是每次 q_insert， console.c 中有以下程式碼：
```cpp
while (use_linenoise && (cmdline = linenoise(prompt))) {
            interpret_cmd(cmdline);
            line_history_add(cmdline);       /* Add to the history. */
            line_history_save(HISTORY_FILE); /* Save the history on disk. */
            line_free(cmdline);
            while (buf_stack && buf_stack->fd != STDIN_FILENO)
                cmd_select(0, NULL, NULL, NULL, NULL);
            has_infile = false;
        }
```
發現類似 corrupted_linked_list.c 的實作，和直譯互動介面的迴圈。
在 qtest.c 中 run_console 函式的 call stack，由 finish_cmd 呼叫 do_quit 函式內實作 cmd_queue 的釋放記憶體。
```cpp
 ok = ok && run_console(infile_name);

    /* Do finish_cmd() before check whether ok is true or false */
    ok = finish_cmd() && ok;

    return !ok;
```
注意到與 free 有關的還有一個 macro ，ADD_COMMAND，是 macro 參數巨集不是函式，功能是類似 Makefile 或是迴圈，或是 sed 系統呼叫，對參數調用 add_cmd(dedup, ...) 函式。參考<前置處理器應用篇> 進行適當文字處理，可以與變數、型別、函式、結構有關。這裡預編譯處理產生文字在原始碼，console_init 這個函式呼叫的 stack 裡。對照2019年程式發現18年到23年才有人發覺老師[提示](https://hackmd.io/@0xff07/SJnc7dtSN?type=view#%E6%96%B0%E5%A2%9E%E5%91%BD%E4%BB%A4)的苦心，不好意思姨母笑了一下。
```cpp
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)

```
雖然有點不道德，但其實考慮鏈結串列結構 cmd_element_t 和 element_t 近乎雷同，do_deque 中的 free 可以稍加改造，就得到 q_free 的實作了，簡直是不勞而獲。另外，考慮 q_quit (at qtest.c:1147) 裡用到 q_free 配合 helper function 處理 queue_contex_t，必須慎選 free 的對象，或是結構的加強，不然恐怕間接會有循環的記憶體缺失，小心為上。 call stack 和函式架構告訴我， console 和 qtest 的 call stack 是分開得，後者有兩層是 Queue 的 queue 很像巢狀迴圈的概念， <vax-r> 有做圖，但有點太多細節了，重點失焦了。
    
### 續：更正名詞和教材更新
 console.h 中的結構體： 多了 para_element_t 一個鏈結串列。<記憶體管理、對齊及硬體特性篇>提到 malloc 和 free 的實作流程。雖然和我們在佇列上的實作相關不大，但要注意。
    
# 繼續佇列運算

參考[惟欣](https://hackmd.io/@weihsinyeh/SJUVTnEn6)筆記，實作 6 基本函式。

## q_reverse

參考[yy]()筆記，搭配[圖解](https://pythontutor.com/render.html#code=%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%0A//%20Define%20a%20simple%20struct%20to%20hold%20an%20integer%20value%0Astruct%20node%20%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node%20*prev%3B%0A%20%20%20%20struct%20node%20*next%3B%0A%7D%3B%0A%0A//%20Function%20to%20add%20a%20new%20node%20to%20the%20end%20of%20the%20list%0Avoid%20add_node%28struct%20node%20**head,%20int%20data%29%20%7B%0A%20%20%20%20struct%20node%20*new_node%20%3D%20%28struct%20node%20*%29%20malloc%28sizeof%28struct%20node%29%29%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%0A%20%20%20%20if%20%28*head%20%3D%3D%20NULL%29%20%7B%0A%20%20%20%20%20%20%20%20*head%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20new_node-%3Eprev%20%3D%20NULL%3B%0A%20%20%20%20%7D%20else%20%7B%0A%20%20%20%20%20%20%20%20struct%20node%20*temp%20%3D%20*head%3B%0A%20%20%20%20%20%20%20%20while%20%28temp-%3Enext%20!%3D%20NULL%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20temp-%3Enext%20%3D%20new_node%3B%0A%20%20%20%20%20%20%20%20new_node-%3Eprev%20%3D%20temp%3B%0A%20%20%20%20%7D%0A%7D%0A%0A//%20Function%20to%20print%20the%20list%0Avoid%20print_list%28struct%20node%20*head%29%20%7B%0A%20%20%20%20while%20%28head%20!%3D%20NULL%29%20%7B%0A%20%20%20%20%20%20%20%20printf%28%22%25d%20%22,%20head-%3Edata%29%3B%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf%28%22%5Cn%22%29%3B%0A%7D%0A%0A//%20Function%20to%20reverse%20the%20linked%20list%0Avoid%20reverse_list%28struct%20node%20**head%29%20%7B%0A%20%20%20%20struct%20node%20*prev%20%3D%20NULL%3B%0A%20%20%20%20struct%20node%20*current%20%3D%20*head%3B%0A%20%20%20%20while%20%28current%20!%3D%20NULL%29%20%7B%0A%20%20%20%20%20%20%20%20struct%20node%20*next_node%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20prev%3B%0A%20%20%20%20%20%20%20%20current-%3Eprev%20%3D%20next_node%3B%0A%20%20%20%20%20%20%20%20prev%20%3D%20current%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20next_node%3B%0A%20%20%20%20%7D%0A%20%20%20%20*head%20%3D%20prev%3B%0A%7D%0A%0Aint%20main%28%29%20%7B%0A%20%20%20%20//%20Create%20a%20list%20and%20add%20some%20nodes%0A%20%20%20%20struct%20node%20*head%20%3D%20NULL%3B%0A%20%20%20%20for%20%28int%20i%20%3D%200%3B%20i%20%3C%203%3B%20i%2B%2B%29%20%7B%0A%20%20%20%20%20%20%20%20add_node%28%26head,%20i%20*%2010%29%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Print%20original%20list%0A%20%20%20%20printf%28%22Original%20list%3A%20%22%29%3B%0A%20%20%20%20print_list%28head%29%3B%0A%0A%20%20%20%20//%20Reverse%20the%20list%0A%20%20%20%20reverse_list%28%26head%29%3B%0A%0A%20%20%20%20//%20Print%20reversed%20list%0A%20%20%20%20printf%28%22Reversed%20list%3A%20%22%29%3B%0A%20%20%20%20print_list%28head%29%3B%0A%0A%20%20%20%20return%200%3B%0A%7D&cumulative=false&curInstr=75&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=c_gcc9.3.0&rawInputLstJSON=%5B%5D&textReferences=false)，只要習慣邏輯和方向，還有暫存的變數，應該問題不大。兩個版本都思考一下。
    
## q_reverseK
參考yy筆記，搭配[圖解](https://hackmd.io/ck7G8AM4Tqy2H7WJDUVo7w?view#reverseK)，只要習慣邏輯和方向，還有暫存的變數，應該問題不大。兩個版本都思考一下。 **q_swap** 視為 `q_reverseK(head, 2)`;
    
## descand
參考[yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_descend)筆記，從後搜尋比大小。 **ascend** 大小相反。
 
## sort
    
yy commit 49e47aa，引入 list_sort 檔案。    
    
## delete_mid
因為不是陣列，或不是哈希表，必須用快慢指標進行。參3考 [yy](https://hackmd.io/@yy214123/linux2025-homework1#q_delete_mid) 結束。[linked_list教材](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-86-Partition-List)
[commit](https://github.com/Urbaner3/lab0-c/commit/990b53e497ec6f1d317422ad747fce7dadcbda89)
    
## delete_dedup
比較 [yy](https://github.com/yy214123/lab0-c/commit/2f84552c32f396bfa90aae8201b31fd4bf31d5a8) 和 [yanjiew](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup) 發現小考有練習，list_cut_position 和 list_splice 很重要。
[vax-r](https://hackmd.io/@vax-r/linux2024-homework1#q_delete_mid) source of 惟欣。

## merge

[Destiny@22](https://hackmd.io/@Destiny0504/linux2022);[git](https://github.com/Destiny0504/lab0-c/commit/97b94ad7b8c2764922687fb841e86bea44419874) 注意， vax-r 寫了很多，~~但不是重點~~，先看 list_sort。 跟 22 年不一樣的程式。再想想。仔細研究 linked list [案例](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)

第六測，和 十七測。./qtest -v 3 -f traces/trace-06.cmd
now decend 錯了。

    
### review
    
[review](https://hackmd.io/@sysprog/linux2025-review) 要求，先做 git rebase 的部分。因為 tig 和 git log 不能一邊看樹的結構，於是我使用 sourcegit 來圖形化，在 fetch 完之後，強制移動 origin/branch 到最新的進度，我讓這個 branch 和 master 一起留在過去的 merge commit，我把 master reset 到最新進度，再用 git branch -f 移動 origin/branch ，因為遠端 fork 的資料夾已經更新完，但 local 的 origin/branch 沒有跟上，當然我必須在 github 網頁上先 sync fork 她才會更新，其實只要切換分支，再 switch 到 origin/branch 最後再 rebase 到最新進度就可以了。有機會再想想命令要怎麼下。 我發現 review 頁面中， rebase 連結的影片都有對剛剛所提及的動作，有所示範及說明，那麼我就不再重複說明，節省時間。
    
![image](https://hackmd.io/_uploads/rJV5Nbw2kl.png)

如果因為 rebase 參考 remote 導致 branch 超前 remote 那只好重建 upstream ，重新同步，才能讓進度同步。嘗試移動分支到 Try 那個 commit 看可不可以 push 。不行就把舊的 remote 刪掉，注意同步關係。
>遇到 push 需要問帳號密碼，要記得做設定。 http 會被要求。改用 ssh。
>git remote set-url origin git@github.com:username/repository.git
    
因為做錯 commit 但已經推上去，想用 revert ，可是並不好。 老師建議 [advice](https://github.com/sysprog21/lab0-c/issues/275#issuecomment-2735260180).`rebase -i` and merge works. 是比 revert好的選擇。
rebase 可以產生新的分支，但同步關係要重設。 merge 錯，把分支調回去，等回收就好。
    
    
# dudect 的統計常數操作分析
    
以信和 yy 都寫執行過程，[惟欣](https://hackmd.io/@weihsinyeh/SJUVTnEn6#%E7%A0%94%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88-Dude-is-my-code-constant-time-%E3%80%89)提到論文分段，還有用 [vestata](https://hackmd.io/@tony268596/linux2024-homework1) 的實作。
作業要求提到兩個問題，(一)解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。(二) 具備 percentile 的處理，但在 lab0-c 則無。當你改進後，可提交 pull request，務必提供對應的數學分析。
    simulation 在 console 中實作，尤其是 insert 和 remove 。我同意 vax-r 同學的見解，但要搭配惟欣的說法才完整說明測試的過程，還有論文的分類。但常數時間執行，還有程式運行得全貌，和數學原理還沒清楚。但我知道寫在[讀我檔案](https://github.com/oreparaz/dudect/tree/master)，想想跟等程式執行的時間有關，沒等到表示超時，非常數時間，有回圈和分支讓他延誤。我發現是因為太多次 simulation 別人一下就跑完，我等五到十分鐘，根本失常，這個失常的統計，就是統計可信的點。
    
用 massif 觀察 simulation 的記憶體用量。
![image](https://hackmd.io/_uploads/SyuTovKnyx.png)

這是 只有 ih, rh 指令的版本。 通過 qtest 所有的佇列運算要求。
    
再去閱讀[Andrew](https://hackmd.io/@andrewchang/linux2025-homework1) 我發現他在 dudect 整理的比較清楚簡單。list_sort.c 他又引用 2023 年 Risheng1128 的結果，我發現後者統計分析的步驟也寫的很好，我雖然未能得到結論，但步驟我的腦袋可以接受，應該跟上。他還有解釋 rio 網路結構的機制。他把 top down 和 bottom up 的方法直接寫在 qsort 之中,也是一個方式。
    
## 網頁伺服器
    
#### select and linenoise IO multitask

```clike
    while(1) {
        if (!async) {
            line = linenoise("hello> ");
            if (line == NULL) break;
        }

```
    
在同步模式下，程序調用 linenoise() 函數顯示提示符 "hello> " 並等待用戶輸入。這個函數會阻塞直到用戶按下 Enter 鍵或使用 Ctrl+C/D 退出。從 github: attr/linenoise 取下的範例。

注意這段話，當中的阻塞，看到這裡我才理解，前後文是對同步或是異步模式中的程序調用。這個程序 process 持續一段時間不會停止，直到相應條件滿足。這樣程序的持續就是阻塞，我一直想成兩件事相互矛盾了。完全錯誤，所以 select 那份作業完全沒有看對啊。 順便把 <C 語言: IO > 一起看了吧。 再回頭看 var-x 同學說 read 阻塞的點，慢慢去想異步處理的那部分程序流程。必須說我們到了一個在觀看瞬時動作的棒球的動作，但為了觀察方便，我們把它靜止，[csdn野史](https://blog.csdn.net/weixin_41028159/article/details/128017480) 加強這個觀念。
>同步，就是我调用一个功能，该功能没有结束前，我死等结果。 
异步，就是我调用一个功能，不需要知道该功能结果，该功能有结果后通知我（回调通知）。 
阻塞，就是调用我（函数），我（函数）没有接收完数据或者没有得到结果之前，我不会返回。 
非阻塞，就是调用我（函数），我（函数）立即返回，通过select通知调用者。

仔細對照後，我認為在 2025年的現在，應該有人嘗試過了，我想知道是誰，過程和結果為何，結果可不可以預測。已知「run_console() 依照 linenoise 開啟與否來選擇要使用 linenoise() 還是 cmd_select()」後面段落已經在 console.c 程式碼裡面了。 而 `grep fcntl` 沒有結果，表示沒有留下，或是放在別的分支裡，要去問出來。

相關 commits:
```csvpreview
5e65cd58 (RinHizakura   2020-09-20 23:54:14 +0800
018ce2e7 (hankluo6      2022-02-25 04:28:10 +0800
ffabd9fa (eecheng87     2022-02-28 13:20:43 +0800
6dccf447 (Jim Huang     2023-02-05 12:15:15
```
「cmd_select() 新增對應的處理」這段落，這邊是需要新增的內容，而且需要根據 web.c 新增標投檔，否則函式會定義錯誤。 process 函式 - linenoise 套件 [不止函式，整份檔案還有標頭檔]。
    
```shell
(base) urbaner@urbaner-wtumagic:~/linux2025/lab0-c$ ./qtest
cmd> web
listen on port 9999, fd is 3
cmd> curl http://localhost:9999/new
Unknown command 'curl'
cmd> 
cmd> 
l = []
cmd> 
Unknown command '.'
cmd> 
l = [1]
cmd> 
l = [2 1]
cmd> 
l = [2 1 3]
cmd> 
l = [1 2 3]
cmd> 
Freeing queue

2001  curl http://localhost:9999/new
 2002  curl http://localhost:9999/ih/1
 2003  curl http://localhost:9999/ih/2
 2004* curl http://localhost:9999/it/3
 2005* curl http://localhost:9999/sort
 2006  curl http://localhost:9999/quit
    
```
簡單修改，以下程式碼即可體驗。
```diff
+++ b/web.c
@@ -257,7 +257,7 @@ int web_eventmux(char *buf)
             accept(server_fd, (struct sockaddr *) &clientaddr, &clientlen);
 
         char *p = web_recv(web_connfd, &clientaddr);
-        char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
+        char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n""<link rel=\"shortcut icon\" href=\"#\">";
         web_send(web_connfd, buffer);
         strncpy(buf, p, strlen(p) + 1);
         free(p);

```
難的是說明還有理解。其實很像聽和說的交互，聽完，要有結束的訊號，比如 over ，說完要有 over 對面如果對等也能聽的話，才知道從哪邊開始停止說，要等前者說完，後者在繼續說，通訊才能完整。 第十章 IO 重點講交互，我看也是講這個，我就一併記起來吧。
[commit](https://github.com/vax-r/lab0-c/commit/b13335b841d9fc482f532f441d64e7729594d204) 把 linenoise 從 select 只能聽幾個檔案建置子，到和 web_socket 較平等的聽說判斷能力，利用 callback 函式幫助。
    
[terminal_IO](https://youtu.be/WcN7ryZYUeQ?si=AuqVMi1ZiDPczU2e) takes control of tty file with format print function and nCurse package escape characters.
    
為了探討 `select(2)` 函式，而 console.c 中， Rio 模型又太複雜，大致而言，是個網路的通訊模型， [CS:APP](https://awesome-programming-books.github.io/computer-system/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F.pdf) 有提到 Web 伺服器。其實如果沒有分身的概念，就是用線程，讓進程做到程序的交互，達成網頁之間的通訊功能，最好從簡單開始，他最基本就是檔案輸出，就是標準的輸出，就是上面 terminal_IO 影片用 tty 嘗試用檔案解釋的概念，但這邊有一個用聊天室軟體，實作結合三種重要的技術， Socket, thread, select 比起 Rio 的 Multitask還要更簡單，只是結束的方法比較陽春，沒有設計好，這部分，可以在跟老師討論，至少這是可以實驗的模型。不到 200 行，嵌入線程和對話迴圈，先後標準調用 socket 和 select 甚至比 tiny-web-server 簡單。專案 [peer](https://github.com/um4ng-tiw/Peer-to-Peer-Socket-C)

研讀 select(2) 並探討 sysprog21/lab0-c 如何偵測程式執行的超時、現有的網頁伺服器如何與 linenoise 並存，以及相關的 signal(7) 使用方式。

## Shuffle 實作
參考 [rota1001](https://hackmd.io/@rota1001/linux2025-homework1#shuffle-%E5%91%BD%E4%BB%A4%E5%AF%A6%E4%BD%9C) 同學， commit [87de389](https://github.com/sysprog21/lab0-c/commit/87de389d6a6b34ea5c482618428c0e34739c817a)，先省略細節考慮 list 函式的動作，發現他在做開頭標頭的插拔和結尾的插拔。
```shell
l = [A B C D E]
cmd> shuffle
l = [B C D E A]
cmd> shuffle
l = [C D E A B]
```
最後把亂數的部分一起看，就知道他在做檢查，條件對了才洗牌。

## list sort 數學分析 論文閱讀
    
關鍵字：
參考：[你不知道：linked list](https://hackmd.io/@sysprog/c-linked-list#Linked-list-%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC); [lab0作業:e](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-e)
    
同學： 邱繼寬 deva ; [共筆規範](https://hackmd.io/@sysprog/linux2025-sample-lab0); 葉惟欣; 鄭以信; 林芸＝[鮭魚](https://hackmd.io/@salmonii/linux2025-homework1#%E6%95%99%E6%9D%90%E9%96%B1%E8%AE%80)

[合作論文分析](https://hackmd.io/@devaraja/paper)
這篇分析寫得很好，多了虛代碼和排序的實例，對於分析實例很有幫助。有把 tail 這個序列（存於陣列)給表現出來，在看論文時，我才了解它跟一般的 merge sort 有什麼不一樣。
>BM 以迭代取代遞迴，並且等全部的子串列被分割之後，由小子串列合併至大的子串列，並且以 p, q 表示目前兩個子串列的頭的索引值。
    
這句話，我第一次看，要個別理解名詞，如迭代，遞迴，子串列，分別代表什麼，還有小子串列。通常這樣解釋很直覺，但是換一個人來看，會需要等待，同步定義後，才能理解這個演算法的意義。等到實際執行後，想一想才能理解它值得注意之處。
>過程中判斷若 q + length >= N 且 q < N 表示剩下元素不足以自己合併出一個 length * 2 長度的子串列，會拿上一個已經合併完成的子串列來合併。           ～～></N>～～

這段話，有把問題的要素提出來，但重點在解釋 q < N 後面的迴圈，對整個串列的效果。    ~~></N>~~
    
我推測，這一連串的演算作法，造成子串列長度都是2 的冪，這樣用標準的 merge sort 每次分的更小的串列長度**保持**2 的冪。
    
接下來，我會嘗試讀一段論文，用自己的方式去解釋，提出來的理論要能夠驗證，對大家才有幫助，就算提出錯誤的作法，或是些細節沒掌握，有一個理論對討論還是有幫助。
    
>去閱讀Andrew 我發現他在 dudect 整理的比較清楚簡單。list_sort.c 他又引用 2023 年 Risheng1128 的結果，   (引用前文)
                   
最後，看到[clh](https://hackmd.io/@clh/linux2025-homework1#%E9%96%B1%E8%AE%80%E8%AB%96%E6%96%87%E3%80%88Dude-is-my-code-constant-time%E3%80%89), 決定盡量照他們的寫法，重新寫一次。太複雜的我就畫在筆記，對照著分頁看，整理起來就好，把筆記拍下來，放在網路相簿。因為他又引用 坤諦江 、Risheng，我把名詞解釋看懂，就不手抄了，把名詞列下來，方便日後查找注意即可。仔細看有個共通點，就是利用5 個節點，簡化抽象狀態，實際執行程式碼的迴圈，去看效果。而且關鍵是 count, pending list 怎樣用 bit 位元去表示狀態。如果任何人，沒有想清楚這些資料的狀態和關聯的話，那就一定是沒有理解。 我發現即使是最聰明的同學，都需要另外把 count 的二進位表示，寫下來，紀錄 pending list 的狀態。另外，tail 是 一個重要的指標，標示目前合併的尾端。我試著操作兩次就好。
    
[rota1101](https://hackmd.io/@rota1001/linux2025-homework1#%E5%AF%A6%E4%BD%9C%E6%96%B9%E5%BC%8F)這裡說的很好：
>這裡因為這個排序中間比較的是字串，所以比較慢，很難去對各種不同的 $n$ 做測試，這裡使用 $n=10000$ 做 100 次測試，即使如此，還是肉眼可見的差異。可以看到，`list_sort` 幾乎都在 $6\times 10^6$ 個 CPU cycle 之內就執行完了。 
![sort](https://hackmd.io/_uploads/HJir16bjyl.png)
這裡同樣能用 t 檢定來驗證 q_sort 的執行時間母體平均比 list_sort 的執行時間長，但由於差異過於明顯，這裡不做這件事。

排序中間比較的是字串，所以比較慢，很難去對各種不同的 $n$ 做測試。亦即複雜度無法歸納為函數。他直接用 CPU 循環數來分析效率。我可以用同樣方法測量 CPU 循環數，做個歸納比較。（參考 Weiso06)
[^nege]:並不是用字串轉換資訊，讓程式在排序的過程中考量進度(batch)當下，記憶體中子序列的節點數目，這樣的方法過度異常。但這和一般排序演算法，考量的變數差異很大，假設我將 merge sort 的分割和合併，過程都記錄下來。看不出這有什麼研究的必要。 
    
    
[^doc] 
[^doc]:文件閱讀[mine](https://hackmd.io/@Urbaner/sortana)
    
## 作業
### git 
用 git 而不是 http 取得遠端的目錄資料。[參考](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github)
[git_alias](https://gitbook.tw/chapters/config/convenient-settings); [recipe](https://gist.github.com/Urbaner3/3d9450d827817bba432fb0cf1f101fac)
    