HackMD2019q1 Homework1 (linux-list)
contributed by < 0xff07 >
開發環境
container_of()
該程式原理類似 qtest 中，使用位址反推 HEADER / FOOTER 的機制。關於該巨集各部份的說明如下：
offsetof()
首先發現一個 offsetof 巨集。查詢 man offsetof 後可以發現關於該巨集的說明：
並且提供範例程式：
由 man 的說明可知該巨集的功能為：給定結構體，以及成員的名稱，offsetof 將給出該成員之位址，與結構體起始位址的差異
({...})
container_of 這個巨集至乍看之下沒有回傳值，但可發現它是一個被小括號包住的復合敘述。這是一個 GCC 的延伸功能。參閱 6.1 Statements and Declarations in Expressions 部份內容可以知道：小括號包住形成複合敘述(coumpound statement)的大括號，在 GCC 中是一個合法的 expression ，該 expression 中最後一個敘述的值，視為該復合敘述計算之後的值。這個延伸功能的其中一個好處是 增加巨集的安全。舉例而言，考慮以下找出兩個 int 中最大值的巨集：
假定想要先將 a 增加 1 ，並找出該結果與 b 較大者，可能會寫出以下程式：
但該程式將會被展開成：
因此在這個巨集當中 a 將會增加兩次，與原先預期不同。但如果使用該延伸功能， 將該巨集改寫成：
a 與 b 中的 expression 都只會被計算一次。而大括號形成的複合敘述，可以使 _a _b 變數的可視範圍限制在大括號中。
整體功能
從巨集後者的：
或許較好理解。該巨集將 member 所在位址，扣除該成員在結構體起始位址的差異，反推回結構體的起始位址。而前面的：
可注意到復合敘述當中的第二行 (type *) ((char *) __pmember - offsetof(type, member)); 與前述的 ((type *) ((char *) (ptr) -offsetof(type, member))) 幾乎相同，
LIST_POISONING
首先查到這個技巧能夠用來除錯。在程式發生未預期的結束時，可以使用 core dump 進行除錯。將刪除的節點設置成某些特定的記憶體位址，若該位址在 core dump 中觀察到被寫入，就可推測問題出在某個 list_head 結構的存取中。
另外查到一個 "memory poisoning"。在 kernel 的文件中，Kernel Self-Protection 的章節提到：
Memory poisoning
When releasing memory, it is best to poison the contents (clear stack on syscall return, wipe heap memory on a free), to avoid reuse attacks that rely on the old contents of memory. This frustrates many uninitialized variable attacks, stack content exposures, heap content exposures, and use-after-free attacks.
所以推測有一部份可能是基於安全考量。
調閱 git log，得知 Linux 核心開發者對 list.h 進行哪些相關修改
:notes: jserv
list_head 的應用
struct task_struct
第一個想到的應用是用於作業系統排程相關。因此第一個想到的就是去查 process control block 相關的結構。因此查到 sched.h 中的 struct task_struct 結構。在這個結構中紀錄許多與行程有關的資料，如 pid, signal handler 等等。當中有許多資訊使用 list_head 儲存。舉例來說：
ptraced 紀錄該程序正在使用 ptrace 觀察的程序們。而當中也有與 perf 相關的資料結構，仍然是用 list_head 建立：
巨集的考量
可發現 list_head 的實作方式，易於擴充，但又可以將所有擴展後的新資料結構，使用同一套巨集進行操作。舉例來說，在 bash 中執行 locate list.h ，試著尋找一些 Linux 核心中使用的相關結構：
以 klist.h 及 plist.h 為例，當中資料結構宣告如下：
文件生成
文件當中註解的符號，原理類似 Doxygen 由特定註解格式自動生成說明文件。但該格式的規範與 Doxygen 不同。在核心的文件中有提到：
The Linux kernel uses Sphinx to generate pretty documentation from reStructuredText files under Documentation. To build the documentation in HTML or PDF formats, use make htmldocs or make pdfdocs. The generated documentation is placed in Documentation/output.
可知該文件生成是使用 sphinx，而非 Doxygen。試著依照指示安裝相依套件：
將會出現需要生成文件所需安裝的相關套件(如指示的連結中說明所提到的)，複製貼上執行即可。若相依套件均已安裝，則會顯示：
安裝完之後，可以考慮安裝文件中指定的佈景主題。但這並非必要(我反而覺得 sphinx 預設主題產生的網頁搜尋功能比較好用)：
接著在核心原始碼的資料夾中執行
待執行完成後，將可以在 Documentation/output 之下，找到文件的 html 輸出結果。
如需搜尋，可以點進 Search.html 中，該網頁提供關鍵字搜尋功能。舉例來說，若搜尋 list_add_tail，則可以找到相關條目：
加入 qtest
這方面的程式放在
lab0裡面 linux-list-test 這個 branch 中。
因為 struct list_head 僅是作為使用者撰寫的 linked list 中的其中一個成員，所以這邊就使用一個包含 struct list_head 的結構體來測試。這邊參考 /private/common.h 中的測試結構體，定義:
因為 list.h 中關鍵的部份是 struct list_head 中的指標操作, 幫物件配置記憶體並不是 list.h 的工作。所以測試的重點在於有沒有正確連接各個指標。
接著， qtest 中使用一個全域的 linked list q 作為待測試的資料結構。這邊也仿照其中的作法，設置一個全域變數 p 作為待測試的結構：
因為 list.h 中並沒有包含如 q_new 之類幫物件配置記憶體空間的操作，但有包含初始化物件的操作，所以這邊不像 qtest 本來的測試宣告一個準備指向 linked list 的指標，而是直接宣告一個 struct listitem。而相較於 queue_t 之前要先 q_new，在測試 listitem 之前要先將其中的 listitem.list 使用 INIT_LIST_HEAD 來初始化。
然後宣告一個 listitem 的陣列作為記憶體池:
再這當中，pool_listitem 陣列是真正存放節點的記憶體空間，pool_valid 表示該對應元素有沒有被使用，如果有的話，就會被設成 true; 而如果要執行類似 free 整個串列連結的操作，只要把所有 pool_valid 設成 false ，並且重新執行 LIST_INIT_HEAD 就好。
觀察：測試 wrapper 的設計
首先觀察一下 qtest 當中的測試函數是怎麼運作的。可以觀察到裡面的函數大多遵循下面這種模式：
幾乎每一個測試函數，最後都會進行 show_queue。因此也先實作對應版本的 show_queue。
show_list
首先實作 show_queue 的對應版本 show_list。首先看一下 show_queue 的程式：
可以發現在遍歷整個 q 時，是用維護好的 qcnt 進行便歷，而不是直接使用 q 的指標操作作為依據。這樣可以檢測出比如「插入通通成功，但刪除通通什麼都沒做」的狀況。如果僅透過指標操作，仍然可以順利遍歷整個 list，也不會發生非法記憶體存取，但這樣並不表示結果正確。而透過維護 qcnt ，遍歷結束之後立刻會發現 cnt 數字對不起來（或是說遍歷完之後發現沒有回到頭等等）。
這邊仿照上述測試，實作 show_list 以及 do_show_list
這邊的邏輯大致與 show_queue 相同，但不一樣之處是：在 queue.h 系列的操作中，會時時刻刻檢查動態配置的記憶體是否正確(即 error_check() 函數)，但這邊因為已經開好陣列了，所以不進行檢查。
do_init_list_head()
接著寫 INIT_LIST_HEAD 的測試：
這邊是用 list_init 作為有沒有初始化的依據，並且在執行結束之後，驗證是否頭尾都連到自己。
do_list_add
這邊的邏輯類似 q_insert 。雖然理論上數字範圍與重複次數應該要是任意的，但在無論限制多寬，本質上還是從 pool_listitem 中的某個元素連接到裡面另外一個元素。所以這邊先規定插入數字 i 時，必須使用 pool_listitem[i] 的記憶體，而範圍只能在 0 ~ POOL_NUM - 1，且一個數字只能插入一次。
大致上來說，架構是檢測輸入, 並在連接之後，對相應的節點做出位置檢查。
