contributed by < yiwei01
>
sysprog2019
一般的 function call 會被 compiler 編譯成組合語言,並且把 function 的參數值、區域變數值以及返回位址 push 進 stack 中,然後再 change control flow 到該 function 所在的記憶體位址,上述過程會有多次的 memory access ,因此程式執行時速度較慢。此外, function 也會被做 type checking 。
macro 則會在 preprocessing 的時候被代換成相對應的程式碼,因此不需要 push function 的參數值、區域變數值以及返回位址進 stack ,也不需要 change control flow ,程式執行速度較快,因此這種會被大量運用的 linked list operation 以 macro 來實作能降低上述 function call 的 overhead 。
另外,inline function 能像 macro 一樣將 function 代換成相對應的程式碼, 但 inline function 是經由 compiler 來代換,所以如果該 inline function 的 code size 太大或為遞迴 function ,則 compiler 會把該 inline function 視為一般 function 。
值得一提的是,在 Linux 核心設計:第一週作業 list (2019-02-25) 中,老師強調了 「 static inline 放在 header file 的用法 」,再去參照 編譯器和最佳化原理篇 後,我得出以下的結論:
因為編譯器在編譯 .c 檔案時視為獨立的個體,所以如果將 inline function 放在某個 .c 檔裡會造成其他 .c 檔 unvisible 的情況,因此應該要放在 header file
因為如果沒加 static , compiler 會認為可能有其他 source file 會 call 這個 function,因此不能被成功代換對應的程式碼到 caller 裡,因為其他 source file 可能也會 call 此 function ,因此沒加 static 的 function 會被 compiler 視為一般 function 編譯
其他參考 : macro 與 function 的優缺比較 、inline function、stackover flow 上的討論
請用 compilation unit 和 symbol visibility 原理去解釋
由 doc 可知 typeof 的 argument 可為 expression 或是 type,在 linux 的 min/max macro 中被用來判別型別是否一致,範例程式碼如下
寫這題前有先看到 HexRabbit 的共筆 ,覺得很多地方寫得很清楚,不過後來看到 這篇 ,思考過後覺得在 HexRabbit 的共筆 中 offsetof
提到 「這裡的 &((TYPE *)0)->MEMBER 並不是求值後取地址,struct 中的成員變數地址是相對於 struct 的初始地址的,並且編譯時期就可以確定也就沒必要在運行時求值了,所以在此得到的是 0 + offset of MEMBER in struct」 這段話跟我的想法有點出入。
先逐一解釋程式碼:
{} :
__typeof__ :
探討 #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
時,先確認一點:「structure 裡的 member 是從 structure 的起始位址開始存放」,測試程式如下:
再來看 (TYPE *)0 其實就是把 address 0 pointer to TYPE 型別,意味著 TYPE 的 starting address 就是從 0 開始,因此 &((TYPE *)0)->MEMBER 就是取 TYPE->MEMBER 的位址,也因為 TYPE 的 starting address 就是從 0 開始,所以 TYPE->MEMBER 的位址就等同於該 MEMBER 與 TYPE 的 starting address 之 offset,最後再將 TYPE->MEMBER 的 address cast 成 size_t 即為結果。
下方的程式碼對 offsetof
做了一些修改,其中 base_x_offsetof
是以 x 當 starting address ,所以所有 MEMBER 都比原本 offsetof
多了 x (本例中的 x 以 10 代入),而 offsetof2
仍以 x 當 starting address ,不過在 cast 成 size_t 後會再減掉 x ,所以會得到與 offsetof
相同的結果。
最後再來看 container_of(ptr, type, member)
,這個 macro 用途在:「當現在只知道某個結構成員的 address ,但想取得整個 structure 的 starting address」時可以使用。
這個 macro 的原理是透過傳遞已知結構成員的 address 給 ptr ,再將 structure 傳給 type ,結構成員傳給 member。因此 __pmember 會保存已知結構成員的 address ,再減掉該結構成員在 structure 中的 offset ,即可知道該 structure 的起始位址。
list.h
還定義一系列操作,為什麼呢?這些有什麼益處?在 linux/inlude/list.h 中,一開始的註解提到:
有了 next/prev 的資訊,能寫出更簡便的程式碼,大大降低寫程式的負擔。
LIST_POISONING
這樣的設計有何意義?先看到 include/linux/list.h 中使用 list_del()
所刪除的 node,其實只是先將其從 linked list 中移除,但該 node 所佔的記憶體區段其實還沒被釋放,因此不該存取 node->prev 或是 node->next ,因為此 node 已經從 linked list 中被移除了,此 node 應被當作 uninitialized,附上 include/linux/list.h 中 list_del()
的程式碼如下:
再來看 include/linux/poison.h 中的註解提到:
LIST_POISONING 是將在一般情況下會造成 page faults 的 non-NULL pointers 指向特定的記憶體位址 (zeroed page),目的是確保未被初始化的 list entries 不會被非法存取。
透過參考 What is the role of LIST_POISON1 and LIST_POISON2? 可知,藉由將 node->next 和 node->prev 指向 LIST_POISON1 及 LIST_POISON2 後,從 list_del()
移除的 node 就是一種會造成 page faults 的 non-NULL pointers,有了這樣的設計便可在 debug 時知道 : 當 error 發生時,若 node->next 與 node->prev 分別指向 LIST_POISON1 與 LIST_POISON2 的話,代表有 use after free 的情況發生,像是 lib/list_debug.c 便是 linux 中對應的除錯程式碼。
若沒有 LIST_POISONING 的設計,在 list_del()
時將 node->next 和 node->prev 都指向 NULL,在 debug 時便不知道此時的 NULL 代表的是 uninitialized 還是被 delete 之後 assign 的。
而不直接將 node free 掉的原因,可在 Kernel Self-Protection 中 Memory poisoning 的部份得知:
When releasing memory, it is best to poison the contents, to avoid reuse attacks that rely on the old contents of memory. E.g., clear stack on a syscall return (CONFIG_GCC_PLUGIN_STACKLEAK), wipe heap memory on a free. This frustrates many uninitialized variable attacks, stack content exposures, heap content exposures, and use-after-free attacks.
在 list.h 中定義了一系列的操作,都是基於環狀 linked list,這篇將 list.h 中的 linked list 的結構以圖示畫出來,十分清楚。因為整個 linked list 中的 head 指標其實不包含 data 的部份,因此對 linked list 的前端或尾端的操作都相當方便,像是「插入」的概念其實就是將 2 個 node 之間多連結 1 個新的 node ,因此 list_add
便是在 head 與 head->next 間插入,而 list_add_tail
則是在 head->prev 與 head 間插入(此處便是利用環狀 linked list 的好處之一),list_del
也不須額外撰寫程式判斷 link list 的邊界情況。
此外, list_add
的行為其實就像是 stack 的 push
,而 list_add_tail
的行為其實就像是 enqueue
。在 list.h 一系列的操作中,可以明顯感受到這類強大的資料封裝技巧。
在 lib/list_sort.c 中可看見 list_sort
如下:
目前想到的是: Quick sort 若選擇第 (n/2) 大的元素作為 pivot ,便可以降低 worst case 發生的機率。
list_for_each_safe
和 list_for_each
的差異在哪?"safe" 在執行時期的影響為何?list_for_each
原始碼如下:
list_for_each_safe
原始碼如下:
兩者的差別主要是在 list_for_each_safe
額外用了 n 這個指向 struct list_head 的 pointer 來紀錄 pos->next ,需要額外用 n 紀錄 pos->next 的理由如下:
考慮透過 list_for_each
搭配 list_del
來將整條 linked list 的 node 移除的情況:
因 list_del
會在移除 node 後,將 node->next 及 node->prev 指向 LIST_POISON 的位址,因此在 list_for_each
的 update statement(pos = pos->next) 便會將 pos 更新為 LIST_POISON 的位址,導致 iteration 無法繼續。(存取 LIST_POISON 位址發生 use after free 的 error)
而 list_for_each_safe
額外用了 n 這個指向 struct list_head 的 pointer 來紀錄 pos->next ,所以 for-loop 的 update statement 執行 pos = n 後,能繼續走訪下一個 node 。
* 提示:對照其他程式語言,如 Perl 和 Python
python for
的用法如下 :
用 C 寫的話 :
兩者的比較 :
比較項目 | python | c |
---|---|---|
array 長度 | 不須考慮 | 須考慮 (上例中的 n ) |
走訪方式 | 直接走訪物件 | 須透過額外的 index 變數 (上例中的 i ) |
@
符號,這有何意義?你能否應用在後續的程式開發呢?Doxygen 能從 source code 的註解產生相對應的文件說明檔,@ 後面為註解命令,例如:@brief 提供一行對於此 function 的簡短描述、@param 作為 function 的參數說明、@return 作為 function 的 return value 的說明等 …。
用法如下:
tests/
目錄底下的 unit test 的作用為何?就軟體工程來說的精神為何?對 include/list.h 提供的 list operation 進行測試,確認各種 list operation 正確執行。
tests/
目錄的 unit test 可如何持續精進和改善呢?閱讀相關檔案
random_shuffle_array
能產生測資,而 listitem 是作為 double-linked list 的 node 。main
函式大致一樣,皆是透過 qsort
排序後的 values 與排序後的 list 進行比對,若有結果不一致則會產生 assertion failure 。程式碼撰寫思路
之前寫 merge-sort 是透過陣列儲存資料,所以會將陣列 divide 成前 (n/2) 個及後 (n/2) 個,不過這次的資料結構是 double-linked list,如果要分成前 (n/2) 個及後 (n/2) 個,我目前想到的方法有三種:
list_for_each
走訪的時候判斷:如果走訪不超過 count/2 ,就 add 到 list_left ,否則就 add 到 list_right 。