contributed by < Naetw
>
看到 macro / function 後最直覺的想法就是,要使用到 macro / function 一定是多段程式碼有其共通性,也就是要把相同的邏輯抽出來,透過 macro / function 做代表,不僅簡化程式碼、更好維護(有問題的話只需修改一個地方),也能用清楚、簡單的名稱來代表一小段程式碼。
兩者的差異:
稍微看過 list.h
後,最明顯的感受是:透過 macro 包裝並將程式碼抽象化,像是將常見的 for each 行為的程式碼用 macro list_for_each
做代替;將常用的對 list 頭、尾的存取行為以 list_first_entry
, list_last_entry
來表示,讓整體對於 list 的操作更加清晰,可以一看見就知道這邊在做什麼樣的事情。
wait_queue
in <linux/wait.h>
不同的行程進入 sleep 的時機、需要被叫醒的條件與時間長度不同,使用 linked list 可以很簡單地新增以及移除整串中間任一節點。此外行程數量也不會是固定的,使用 linked list 可以增加彈性。
parse_events.c
perf 預設是觀察 cycles,但是可以透過參數去指定說要監控哪些事件,而事件的長度非固定,透過 list 可以彈性的管理。
select.c
在撰寫網路應用程式時,常需要透過 poll
/ select
來對既有的連線做管理,同樣的 list 可以做到彈性管理,像是突然有新的連線或是舊有連線離開的操作都可以很簡單透過 list 達成。
可以獲得運算式的型別。
container_of
list_for_each_entry
系列
struct list_head
就能夠去做串聯。然而不同結構中 list_head
型別的成員會位在不同位置。此巨集系列的作用為走訪各個 entry,顧名思義我們需要利用 entry 型別裡的成員 list_head
去做走訪,同時走訪過程中的操作是對於 entry 本身,也就是需要去拿到不同節點的 entry 開頭位址,這個位址可以利用上面提到的 container_of
來去獲得,而要使用 container_of
的很重要的一個參數就是需要提供整個結構的型別,typeof
可以幫忙做到這件事。container_of
的原理container_of
透過成員位址來推算出物件的開頭位址。
ptr
- 指向成員的指標,也就是描述中的「成員位址」type
- 包含該成員的結構型別member
- 成員變數名稱__extension__
用途GNU C 支援了很多 extensions,若編譯參數裡有加上 pedantic
的話,編譯器會警告所有違反標準 C 語言的寫法。若在運算式(expression)前加上 __extension__
便可以達到白名單的效果。
在 __extension__
後有個奇怪的結構 - ({})
,可以將括號內整體視作一個運算式,這同樣是 GNU C 的 extension,加上括號後我們可以在 compound statements 中加入像是迴圈、switch,或是區域變數的使用;此外,它會以區塊中最後一個陳述式的作為此運算式的結果。
首先來看 __pmember
的型別,它是一個 pointer to xxxx that is const,而 xxxx 就是 __typeof__()
所獲得的型別,typeof
的運算子簡單來說就是 type
這個型別中的成員 member
的型別。因此,正常來說 __pmember
這個指標所指向的型別「應該」要與 ptr
是相同的。
如此一來疑問就來了,這行陳述式存在的意義?實際上就如同上面所描述的:「它們兩個所指向的型別應該要相同」,因為我們無法保證傳入的參數是正確的,而這個指派的動作可以讓編譯器去做型別檢查。若程式設計師的參數不小心寫錯了,那麼在編譯時期就能夠找到這個錯誤,進而去修正。
__pmember
在正常情況下就會是某個型別中的某成員位址,透過標準函式庫中的 offsetof
來獲得該成員相對於整個物件的偏移,將這個偏移量扣除,就能夠獲得物件的開頭位址。需特別注意的部分是強制轉型為 (char *)
的部分,因為想要達成的操作是純量的減法,所以需要將它的做轉型為 pointer to 某個大小為 1 byte 的型別,若沒有強制轉型,減法做完會是往前 offsetof
個原型別物件的位址。
list_del_init
list_del
後,被解除連結的節點空間並不會被釋放與重新設定,若之後不小心直接使用到該節點,有可能會動到不該動的資料,於是有了 list_del_init
的設計,這個函式除了執行 list_del
外,還會將被刪除的節點重新設定成初始狀態。list_empty
head->next == head
的行為做包裝,讓程式碼能夠更一目瞭然。list_is_singular
list_splice
系列
init
的會將來源的節點重新設定,避免誤用。list_cut_position
整體來說,就是將常用到的操作給抽象化,讓程式碼寫起來更為簡潔且清楚。
故意給個有問題的記憶體位址,若之後直接使用到沒有好好重新設定的節點,會觸發 segmentation fault。個人認為設計用意是:與其讓不安全且不確定的行為可以繼續往下執行,不如讓它發生錯誤。
思考透過 gdb/kgdb 除錯時,POISONING 的幫助,核心已經考慮進去了
選擇 0x00100100
的用意可參考 kernel debugging wiki。
使用 gdb 除錯時,若使用 print
指令印出變數內容時,看到特別的數值(像是上方的 0x00100100
)查閱手冊就可以知道遇到什麼問題,不同數值代表不同的錯誤操作。
打算使用 quick select 的方式,並搭配選擇中位數作為 pivot 避免最糟情況。
list_for_each_safe
和 list_for_each
的差異在哪?“safe” 在執行時期的影響為何?多使用一個變數來儲存下一個節點。沒有 safe 的設計限制不能對 list 有任何的修改,有了 safe 的幫助可以做到刪除當前節點的動作。
幫助紀錄下一個節點位址,需要幫忙的原因:
list_del
做刪除
malloc
來獲得空間的話,並有透過 free
釋放空間時,glibc 內部管理 heap 是有特別的機制的,像是 fastbin
, smallbin
等等,在這套機制的使用下,節點的內容在被釋放後是會被修改的,也因此無法保證在刪除並釋放空間後內部的資訊還是跟之前一樣。heap 機制可參考 Heap Exploitation by Angelboy。list_del_init
做刪除
list_head
結構,若沒有 safe 的幫助,便拿不到下一個節點的位址。針對程式碼中各個模組做正確性檢驗。有了 unit test,往後若需要重構時,能夠確保修改後的程式碼運行結果跟之前的一樣。
在撰寫上方的自我檢查清單時,即便能理解行為但對於整個 linked list 的設計仍十分的不習慣與陌生,導致在寫程式的時候常常是把類似的行為做到一半或做完才想到可以用 list.h
提供的一系列操作。
基本上就跟一般的合併排序實作一樣,列出幾個差異:
合併排序需要將整個序列不斷對半切成較小的子問題來處理,最後再將結果做合併 (divide & conquer)。這對一般的陣列來說十分簡單,只需要求得陣列長度並做單純的運算即可,但是 linked list 需要實際去走訪總長度並獲得中間節點。
獲得總長度與獲得中間節點看似需要兩次走訪,實際上不用,利用共筆 - 你所不知道的C語言: linked list 和非連續記憶體操作裡所提到的龜兔賽跑 (Floyd’s algorithm),可以很簡單的找到 list 長度,同時又能獲得中間節點的位址。
兔子 (fast) 一次走兩格,烏龜 (slow) 一次走一格,兔子只需要花 N 個迴圈次數便可以走完 list,而烏龜此時剛好就只走了 N,也就是我們需要的中間節點。
跳離迴圈後,使用 list.h
提供的 list_cut_position
來對串列切半,接著用 list_splice
來轉移後半段子串列擁有權。
list_move_tail
來做節點的擁有權轉移即可list_splice_tail
轉移整條擁有權。在使用 gnuplot 前,修改了 lab0-c 的 driver.py 來自動跑三種排序演算法並產生出相對應的資料:
接著撰寫 gnuplot 腳本。
首先是設定圖的標示,可以使用 xlabel
, ylabel
來設定 x, y 軸的名稱、設定 x 軸的刻度間距,以及 title
來設定標題,最後是輸出檔案的檔名:
還有其他設定可以進入 gnuplot 後輸入指令 help
來查詢,或是參考共筆 gnuplot 語法解說和示範。
接著是繪圖相關的指令,plot
為繪圖的指令,後面需接上各種參數來描述怎麼取出資料並以什麼種類的圖來呈現,首先來看語法:
以下方腳本來說明:
[:][:]
plot [<xrange>][<yrange>][<x2range>][<y2range>] ...
[-1:]
'normal.txt'
using 1:2
1:2
代表 x 軸使用 1st column 而 y 軸使用 2nd column 的資料using (column("merge-sort")):(column(1))
或是 using "Size":"merge-sort"
with linespoints linewidth 2
help plot style
查看第一手資料!plot
指令需要是單一行指令,可以利用反斜線來增加可讀性,就像上方那樣分行
另外如果是取用同一個資料檔,那後面可以單獨使用 ''
就相當於一開始的 'normal.txt'
首先是安裝 git hook:
GIT_HOOK
為某個檔案路徑,用來作為 target
scripts/install-git-hooks
可以看到在安裝到最後會創建一個空的檔案 .git/hooks/applied
用來代表成功安裝。$(GIT_HOOK)
中利用 Makefile 的 magic 變數 $<
來執行安裝腳本
$<
代表的是 first prerequisite@
是一個指令前綴,代表的是:不要印出指令本身接著是一些比較簡單的設定:
.PHONY
來指定 target 為 fake 項目,如此一來 make
才不會去檢查該目錄中是否存在該 target 名稱的檔案all
的前置條件為 Git hook 與 check 的執行.DEFAULT_GOAL
來指定沒有加任何參數的純 make
指令所需要執行的 target(預設會是最上面的 target)include
就跟 C 裡面見到的差不多,可以引入其他的 MakefileCFLAGS
變數設定關於主要的單元測試檔案相關變數設定:
TESTS
就是一連串巨集 / 函式的名稱所組成的字串(以空白為區隔)addprefix
幫現有的 TESTS
變數裡面的所有名稱加上 prefix 'tests/'
$(addprefix prefix,names…)
deps
變數的用法翻了翻 GNU make 的手冊翻不太到,跑去翻了 git log,看起來應該是寫錯?第二個 :
應該要是 =
?echo
來看他的內容是空的
deps := $(TESTS:%=%.o.d)
的作用是,將 $(TESTS)
中所有內容加上 suffix .o.d
。這種用法稱為 Substitution Referencesdeps
只有在最後一行被 include
指令使用,詳見下方的「自動產生相依性項目」預設規則的主軸:
%
但效果是相同的,也就是將 TESTS
變數裡的所有名稱加上 suffix .ok
簡單來說就是能夠提供一個 targets 列表,接著利用 target-pattern 去篩選並獲得想要的資訊,然後再重組成相依性項目。
在這邊的例子是利用 '%'
來獲得 targets 的 stem,也就是 xxx.ok
中的 xxx
,然後把這個 xxx
當作相依性項目。所以實際上我們相當於擁有下列規則:
common.mk
中,與變數 VECHO 都是用來決定 verbosity,簡單來說就是決定輸出的資訊量多寡,而變數 PRINTF 內容為因應不同環境使用該環境的 printf 指令xxx.ok
來表示驗證完成確定了上方 $(TESTS_OK)
targets 的相依性項目都是各個函式或巨集的單元測試執行檔,那最後就是這些執行檔是怎麼被 make 出來的:
%.o: %.c
,利用 Pattern Rules 中的 '%'
符號來獲得 "stem"-c
不要跑連結器 (linker)-MMD
閱讀手冊發現其實它等價於 -MM -MF file
,-MMD
會透過 -o
所指定的檔名去加上 suffix .d
來當作 -MF file
中的 file-MF file
當使用 -M
/ -MM
來讓編譯器產生 Makefile 的相依性項目時,可以使用此選項指定要把相依性項目的內容寫到特定檔案$(TESTS_OK)
去跑測試平常對自己的 C 專案撰寫 Makefile 時,常常都是人工慢慢新增或刪除相依性項目 (prerequisite),如此一來當專案規模增大時,是十分麻煩且容易出錯的。
在過去,一般會利用編譯器的選項 -M
來產生原始碼所需要的 Makefile rules,並在主要的 Makefile 中用 target depend 來完成這件事,最後用 include
指令來把產生的 depend 檔案(是一種 Makefile)引入。
舉例來說(假設 main.c 裡面沒有引入任何檔案):
會產生如下面的輸出:
若 main.c
中有引入其他檔案,則輸出就會增加有引入的所有檔案。
現今在 GNU make 的官網建議是:針對每個原始碼檔案 name.c
都有各自的一個 Makefile name.d
對應,內容就是目的檔 name.o
與 Makefile name.d
的相依檔案列表,如此一來,只有當原始碼有更動到,才需要去更新此特定的 Makefile。
下方是用來產生相依性項目檔案(本質上是個 Makefile)的 pattern rule:
編號即代表各行數的指令。
.d
Makefile(註:$@
代表的是 target name).c
檔,並用前面提到的 -M
選項產生相依性項目,最後寫入 <target>.$$$$
(註:$<
代表相依性項目中的第一個項目,在這裡就是被編譯的檔案名稱)
-MM
,這個選項不會把系統的標頭檔也一起寫進相依性項目中sed
可以使用任意字元作為 delimiter 來避免讓實際要做替換的字串太過複雜(需要一堆反斜線)。在這邊就是使用 ,
作為 delimiter。
$*
,手冊翻了很久、Google 也查不太到。最後發現去年底發佈的 4.6 版本有除錯模式,直接拿來看執行細節,試了幾次後,嚴重懷疑那段是寫錯的。根據取代中的 \1
的使用,推測 \($*\)\.o
中的 .o
前面的行為是想要去抓到 .o
前的所有字串,後面再用 \1
去做 back reference,但是其實根本不需要。sed 這邊的取代行為基本上跟 vim 裡面一樣,可以直接用 \.o[ :]*
取代成 \.o $@ :
也會有一樣的效果。被這個沒有用途又應該是寫錯的語法雷了好久 Orz簡單來說 5. 想做到的事情是將下列的 Makefile 內容作改寫:
改成:
簡單來說就是在 .o
跟 :
中插入 $@
(target name),因此第 4 行的 sed
指令可以改成:
到此已經產生好專屬的 Makefile main.d
,裡面包含了 main.o
的 remake 規則(當 main.c
or defs.h
有更動時要更新),而 main.d
也具有同樣的 remake 規則。這時透過 Makefile 中的 include
指令,將此 Makefile main.d
引入進去,make
就能夠自動判斷什麼時候要重新製作關於 main.o
的相依性項目,同時也會更新 main.d
,使用者再也不需要手動處理。