HackMD2025q1 Homework1 (lab0)
contributed by < Urbaner3 >
開發環境
$ 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
新聞
準備工具與材料
yy 我和他一樣重頭砍掉重練。
<chennship> harness 提到要解決記憶體問題，第一次就注意到不簡單。跟著做。
共筆規範 太誇張了，竟然寫的這麼清楚，想想覺得壓力很大，不努力不行。參考 < BigMickey > 的筆記，像我以前一樣，方格接近流水帳，用 commit 來省略比較簡潔，共筆需要的是溝通，流水帳最多是給助教看吧。我決定把流水帳的筆記稱作童話故事，會有完整的細節，應該很亂。這裡是現實。
參考材料
這裡簡單列一些重要材料，<指標篇>、 <linked_list 篇>。附錄 container_of 篇。前置處理器篇，告訴我 header 檔案的歷史。我8日凌晨還看了很多影片，記在日曆上面。 為了瞭解 <yy> 他為什麼會去思考更改 harness 檔案， 我看了…
動態配置記憶體1 mycodeschool 記憶體分區 Ryan Baker 兩部影片說明動態記憶體配置的形態，概念，這讓我想到<記憶體管理…特性篇>，還有<每位程式開發者都該有的記憶體配置> 和在一起看，共筆規範、<chensheep>、<yy> 他們刻意處理 q_free 的部分，記憶體對齊錯誤的問題，就有了線索，我決定先做到 make check 有關的運算就好不然我記不住了，記憶體不足。會記錯和迷失。
qcheck: qtest
./$< -v 3 -f traces/trace-eg.cmd
qtest: $(OBJS)
$(VECHO) " LD\t$@\n"
$(Q)$(CC) $(LDFLAGS) -o $@ $^ -lm
因為我無法預測 Makefile 自動化編排的機制，所以我用 GPT 去執行翻譯，前後線索我整理不起來，很多猜測人心的桌遊，比如風聲，我不擅長。結果是：
# 建立編譯暫存目錄
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 做鏈結佇列的相關運算，把過去記錄備著繼續進行。想到還有藍圖 和 重做 lab0 專案低能參考。
(https://hackmd.io/@sysprog/linux2024-projects#重做-lab0-並彙整學員成果)7份。
接下來要講的很重要，是整份專案當中最危險，需要耐心多讀幾次的。 就是作業解說二 <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)
- 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
test_malloc 函式實作如下:
"">>>>>>"從這裡開始
根據 commit f087e77 <
komark06> 利用 alloc 相關物件宣告改變了test_malloc函式的實作。後者即為alloc函式的合成，其實作為：
void *test_malloc(size_t size)
{
return alloc(TEST_MALLOC, size);
}
其中，alloc 函式實作如下：
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_ttype 型別。另外搜索 'linux kernelblock_element_t' ，會發現原始文件版本，出自一位 <0xff07> 學長，很多細節值得一看。另外，當年設定 ` 那時候的 ELE 就是今天的 element， 在 queue.h 理頭。
"">>>>>>"到這裡
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 配置的空間，示意如下圖:
- 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
gcc 的擴充功能 "Arrays of Length Zero" 在 Linux 核心大量使用，可參照中文解說 C Struct Hack - Structure with variable length array
注意，講師 jserv 有為了凸顯項目符號 1. 讓段落縮排，我只是呈現內容，略去前者的操作。
整理架構
竟然有名詞的改動，而且是老師的行動，那值得深究。用grep -r element 搜尋檔案，找一些重要的鏈結串列，都是雙向侵入式鏈結串列。
queue.h:} element_t;
console.h:} cmd_element_t;
console.h:} param_element_t;
harness.c:} block_element_t;
為了測試並了解教材的操作，我去抓取原版程式
search "gdb call stack command",page with 2 examples call_stack.c and corrupted_linked_list.c
call stack using the where, up, down and frame commands.
經過整理教材後，我知道危險之處在哪理了。這邊有些段落從原始文章引用，細看可以發現，順序有點簡化，前後有些不對應。
gdb ./qtest
cmd> run -> new -> ih hello
ctrl - C sends singal, 會得到畫面：
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
(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 用自己寫法定義一些自己方便的說法，讓自己熟悉了解記憶體的建立和刪去。昨天測試的也是好例子。
Valgrind 嘗試修正 leak
理解修正的狀況之後，才有辦法修正 direct memory leak。
(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 結束迴圈。
(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 工具，搭配 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 的函式就可以了。
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 中有以下程式碼：
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 的釋放記憶體。
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年才有人發覺老師提示的苦心，不好意思姨母笑了一下。
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 的實作流程。雖然和我們在佇列上的實作相關不大，但要注意。
繼續佇列運算
參考惟欣筆記，實作 6 基本函式。
q_reverse
參考yy筆記，搭配圖解，只要習慣邏輯和方向，還有暫存的變數，應該問題不大。兩個版本都思考一下。
q_reverseK
參考yy筆記，搭配圖解，只要習慣邏輯和方向，還有暫存的變數，應該問題不大。兩個版本都思考一下。 q_swap 視為 q_reverseK(head, 2);
descand
參考yanjiew筆記，從後搜尋比大小。 ascend 大小相反。
sort
yy commit 49e47aa，引入 list_sort 檔案。
delete_mid
因為不是陣列，或不是哈希表，必須用快慢指標進行。參3考 yy 結束。教材
commit
delete_dedup
比較 yy 和 yanjiew 發現小考有練習，list_cut_position 和 list_splice 很重要。
vax-r source of 惟欣。
merge
Destiny@22;git 注意， vax-r 寫了很多，但不是重點，先看 list_sort。 跟 22 年不一樣的程式。再想想。仔細研究 linked list 案例
第六測，和 十七測。./qtest -v 3 -f traces/trace-06.cmd
now decend 錯了。
review
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 連結的影片都有對剛剛所提及的動作，有所示範及說明，那麼我就不再重複說明，節省時間。
如果因為 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.rebase -i and merge works. 是比 revert好的選擇。
rebase 可以產生新的分支，但同步關係要重設。 merge 錯，把分支調回去，等回收就好。
dudect 的統計常數操作分析
以信和 yy 都寫執行過程，惟欣提到論文分段，還有用 vestata 的實作。
作業要求提到兩個問題，(一)解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。(二) 具備 percentile 的處理，但在 lab0-c 則無。當你改進後，可提交 pull request，務必提供對應的數學分析。
simulation 在 console 中實作，尤其是 insert 和 remove 。我同意 vax-r 同學的見解，但要搭配惟欣的說法才完整說明測試的過程，還有論文的分類。但常數時間執行，還有程式運行得全貌，和數學原理還沒清楚。但我知道寫在讀我檔案，想想跟等程式執行的時間有關，沒等到表示超時，非常數時間，有回圈和分支讓他延誤。我發現是因為太多次 simulation 別人一下就跑完，我等五到十分鐘，根本失常，這個失常的統計，就是統計可信的點。
用 massif 觀察 simulation 的記憶體用量。
這是 只有 ih, rh 指令的版本。 通過 qtest 所有的佇列運算要求。
