# 2024q1 Homework1 (lab0)
contributed by < `BooleanII` >
## 開發環境
### WSL 開發環境版本
:::danger
改進你的漢語表達。
:::
手邊沒有閒置的電腦可以安裝 Ubuntu 實體機，先以 Win10 WSL 虛擬機獲得 Ubuntu 22.04.03 LTS測試。
```
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ 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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
CPU family: 6
Model: 60
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
Stepping: 3
BogoMIPS: 5187.99
```
:::danger
每天用 Linux，自然就會變強，拿出你的決心來。
:::
購置新的電腦安裝 Ubuntu 實體機，安裝前須先關閉 `bitlocker` 與快速開機設定，否則會免費驗一次 bitlocker 解除流程，硬碟磁碟區可使用壓縮硬碟方式從 C 槽分割出想要的空間。 `boot loader` 位址選擇硬碟的根目錄，並將方才分割出的空間指定為 `/` 目錄， home 與 swap 目錄空間不需額外指派，安裝完成後重新開機進入 Ubuntu 系統就大功告成了。剩餘的環境建安裝流程相較 WSL2 順利不少。
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ 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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i3-1215U
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 4
CPU max MHz: 4400.0000
CPU min MHz: 400.0000
BogoMIPS: 4992.00
```
### WSL Perf 安裝
參照教學流程安裝 linux-tools-common 後， perf list 命令獲得的結果共列出四樣東西需要安裝，然而每一樣 package 皆無法在 WSL 下順利安裝。在網路上找到許多方法，但實際操作僅有手動下載 WSL2 Kernel 並編譯 perf 可以解決問題。
```shell
$ perf list
WARNING: perf not found for kernel 5.15.133.1-microsoft
You may need ot install the following packages for this specific kernel:
linux-tools-5.15.133.1-microsoft-standard-WSL2
linux-clout-tools-5.15.133.1-microsoft-standard-WSL2
You my also want to insall one of the following packages to keep up to date:
linux-tools-standard-WSL2
linux-cloud-tools-standard-WSL2
```
> [WSL下手動編譯安裝Perf](https://gist.github.com/abel0b/b1881e41b9e1c4b16d84e5e083c38a13)
> [在WSL2中使用perf性能剖析工具](https://zhuanlan.zhihu.com/p/600483539)
:::danger
1. 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
2. 留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
:::
## 佇列操作程式碼實作
### `q_insert_head`
使用自行建立的 e_new 函式 malloc 新的資料節點，佇列成員以 INIT_LIST_HEAD 進行初始化。~~字串使用 strncpy 取代 strcpy 避免不安全的記憶體操作~~ 字串使用 strncpy 進行複製，避免 strcpy 的不安全記憶體操作風險。
:::danger
改進你的漢語表達。
:::
> [依據 CERN Common vulnerabilities guide for C programmers 建議而移除 gets / sprintf / strcpy 等不安全的函式](https://hackmd.io/@sysprog/linux2024-lab0-a#M01-lab0)
### `q_insert_tail`
與 q_insert_head 大同小異，改呼叫 `list_add_tail` 函式以 FIFO 方式加入。
### `q_free`
透過 list_for_each_entry_safe 巨集，可走訪整個佇列並對佇列內容進行更動，巨集所使用的變數如下：
- @entry：資料節點，在這專案中為 element_t 結構
- @safe：佇列中的下一個資料節點，在這專案中為 element_t 結構
- @head：使用 container_of 巨集功能找尋的成員位址
- @member：使用 container_of 巨集功能找尋的成員名稱
由於 `element_t` 結構體中， value 成員與資料節點使用 malloc 獲得，故需對這兩者的記憶體位置進行釋放，最後也要記得將 head 的記憶體位置釋放。
### `q_remove_head`
使用 `strncpy` 進行字串的複製，會遇到當資料節點的字串長度小於 bufsize 時，剩餘的長度資料會被填0替代，故加入判斷式避免 sp 的字串與原始資料不符。
```c
if (strsize <= bufsize)
strncpy(sp, element->value, strsize + 1);
else {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize] = '\0';
}
```
### `q_delete_mid`
:::danger
留意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
分別使用兩個 list_head 指標( forward, backward )以相反的方向走訪佇列，當兩個指標相遇時， foward 的位置即為要刪除的資料節點。
```c
struct list_head *forward = head->next, *backward = head->prev;
while(forward->next != backward && forward != backward) {
forward = forward->next;
backward = backward->prev;
}
element_t *element = list_entry(forward, element_t, list);
```
### `q_swap`
參考 [millaker](https://github.com/millaker/lab0-c)，發現使用 list_del 後的程式碼看起來簡潔一些。基於他的程式碼再做點改進，呼叫 list_add 讓整個思路更加明瞭。後來發現到這個其實就是 list_move 函式...
```c
struct list_head *first = head->next, *second = head->next->next;
while(first != head && second != head) {
list_del(first);
list_add(first, second)
first = first->next;
second = first->next;
}
```
:::danger
使用作業指定的程式碼縮排風格
:::
```c
struct list_head *first = head->next, *second = head->next->next;
while (first != head && second != head) {
list_move(first, second);
first = first->next;
second = first->next;
}
```
### `q_reverseK`
輸入參數 k 的群組節點數量應大於1才需要進行 reverse 動作。一開始想到的方法是用 for 迴圈找出群組的起始與結束節點，再從兩端進行節點的互換，但這麼做會用到大量的暫存參數。換個角度思考，可以將群組切割為群組佇列，再使用先前實作的 `q_reverse` 進行反轉。
lins.h 中提供的 `list_cut_position` 可以實作佇列切割的功能，輸入參數說明如下：
- `@head_to` ：切割後的佇列指標，傳入前可不需執行 `INIT_LIST_HEAD` 初始化，函式執行後將儲存來源佇列的第一個資料節點到切割的資料節點
- `@head_from` ：來源佇列指標，函式執行後將儲存切割的資料節點後方剩餘的資料節點
- `@node` ：切割的資料節點。
須注意 list_cut_position 的例外條件有二，第一個為來源佇列無資料節點；第二個為切割的資料節點是來源佇列的頭節點。
```c
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
群組佇列反轉後，使用 list.h 中的 `list_splice_tail` 儲存於暫存的佇列中，並重複切割、反轉與儲存 head 剩餘的群組佇列，如來源佇列的剩餘節點數量不足以組成一個群組，仍執行佇列分割但不進行反轉，最後呼叫 `list_splice` 將群組佇列接回到原始的佇列中。深刻感受到 list.h 提供許多好用的函式，搞懂並活用可以加快寫作業的速度。
```c
do {
cut_point = head->next;
for (i = 1; i < k && cut_point != head; i++)
cut_point = cut_point->next;
list_cut_position(&group, head,
(cut_point == head) ? cut_point->prev : cut_point);
if (cut_point != head)
q_reverse(&group);
list_splice_tail(&group, &tmp);
} while (!list_empty(head));
list_splice(&tmp, head);
```
### `q_descend`
```
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
```
:::danger
給定的佇列具備雙向且環狀的屬性，你不該說「反向」，改用更精準的詞彙，寧可用更多的詞彙和描述，務必降低誤解，此乃工程協作之關鍵素養。
:::
在 leetcode 進行測試確認函式的邏輯，發現可以透過<s>反向</s>往 `prev` 方向走訪佇列來實作。當~~左方~~ prev 的資料節點**小於等於**當下的資料節點時( `q_ascend` 的判斷機制則為**大於等於**)，呼叫 `list_del` 將該節點自佇列中 `remove` ，並重複上述行為直到佇列的開頭。走訪方式參考 `list_for_each_safe` 進行實作。
測試程式功能時，發現在離開 qtest 或執行 free 命令， qtest 會顯示有空間未被正常釋放，顯示題目的需求為 `delete` 非 `remove` ，建議將函式的描述用詞進行修改避免混淆。
```
ERROR: Freed queue, but 2 blocks are still allocated
```
```c
int count = 1, cmp;
struct list_head *safe, *second, *first = head->prev;
for (second = first->prev, safe = second->prev; second != head;
second = safe, safe = second->prev) {
cmp = strcmp(list_entry(second, element_t, list)->value,
list_entry(first, element_t, list)->value);
if (cmp >= 0) {
count++;
first = second;
} else {
list_del(second);
q_release_element(list_entry(second, element_t, list));
}
}
```
### `q_delete_dup`
參照 leetcode [`82. Remove Duplicates from Sorted List II`](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/) 題目說明，刪除`已完成排序`佇列中的 `value` 相同的節點。
由於是對已完成排序的佇列進行處理，內容為相同 vaule 的節點必定相鄰，讓實作的方法簡單很多。透過 list_for_each_safe 走訪整個佇列，以 list_head 結構體 `dup_beg` 與 `dup_end` 紀錄相同 value 節點的起始節點與結束節點， dup_beg 與 dup_end 相同時代表目前無兩個以上 value 相同的節點。若遇到內容為相同 value 的節點時，則 dep_end 會指向該節點。
若走訪的節點 visit 與下一個節點 visit_next 的字串不同，且 dup_beg 與 dup_end 指向的節點也不同時，代表有重複的節點要進行刪除，將 dup_beg 到 dup_end 之間的節點移至 head_delete 下，並參照 q_free 的實作方法把 head_delete 中的節點刪除。
由於 list_for_each_safe 的結束條件為 visit!=head ，需要處理走訪到最後一個節點時的特殊案例，避免 head 與最後一個節點的 value 進行比較引發 segmentation fault 。
```c
list_for_each_safe (visit, visit_next, head) {
if (visit_next == head ||
strcmp(list_entry(visit, element_t, list)->value,
list_entry(visit_next, element_t, list)->value)) {
if (dup_beg != dup_end) {
dup_beg->prev->next = dup_end->next;
dup_end->next->prev = dup_beg->prev;
head_delete->next = dup_beg;
head_delete->prev = dup_end;
dup_beg->prev = head_delete;
dup_end->next = head_delete;
element_t *entry, *entry_next;
list_for_each_entry_safe (entry, entry_next, head_delete,
list) {
free(entry->value);
free(entry);
}
}
dup_beg = visit_next;
}
dup_end = visit_next;
}
```
### `q_merge`
函式功能參照 leetcode [`23. Merge k Sorted Lists`](https://leetcode.com/problems/merge-k-sorted-lists/) 題目內容，將已完成排序的佇列合併至第一個佇列。 需注意此函式的輸入僅有 struct list_head 指標與決定合併順序的 bool 參數，這是因為 qtest 中的所有佇列使用 queue_contex_t 結構體進行儲存，其架構與 linux kernel 的環狀佇列相似，第一個開頭結構體中未儲存資料。
queue_contex_t 結構體的 chain 成員用於實現 queue_context_t 環狀佇列，函式的 head 輸入即為此成員； q 成員則是資料佇列的 head ； id 成員用於標示 queue_contex_t 節點的代號； size 成員用於儲存 q 成員中的資料節點數量 (不包含head)。
由於所有的資料佇列皆已完成排序，可透過走訪 queue_contex_t 佇列，比較每個資料佇列的第一個資料節點，依據函式輸入的 descend 參數，找出所有資料佇列中最小或最大的資料節點。透過 list_del 與 list_splice_tail 函式將該資料節點取出並加入用於暫時儲存最終合併的 sorted 佇列中。當所有的資料佇列內皆無資料節點，代表已完成佇列合併，可呼叫 list_splice 函式將 sorted 佇列中的節點儲存至 queue_contex_t 佇列的第一個資料節點內。
```c
while (1) {
struct list_head *ins_node = NULL, *cmp_node = NULL;
list_for_each (node, head) {
if (list_empty(list_entry(node, queue_contex_t, chain)->q))
continue;
cmp_node = list_entry(node, queue_contex_t, chain)->q->next;
if (!ins_node) {
ins_node = cmp_node;
} else if (compare(ins_node, cmp_node, descend) >= 0) {
ins_node = cmp_node;
}
}
if (!ins_node)
break;
list_del(ins_node);
list_add_tail(ins_node, &sorted);
cnt++;
}
list_splice(&sorted, list_entry(head->next, queue_contex_t, chain)->q);
```
後記：
一開始想到的合併方式較為繁瑣難以透過簡潔的程式碼達成，合併流程是將在 queue_contex_t chain 中走訪到的第一個佇列作為 sorted 佇列，透過走訪 sorted 佇列的資料節點與下一個合併對象的佇列資料節點進行比較，當找到可以合併的資料節點時，改走訪合併對象的佇列，透過 list_del 與 list_splice 將可合併的資料節點進行合併。當合併對象佇列的資料節點不滿足合併條件時，再回到 sorted 佇列走訪剩餘的節點，若合併對象佇列在 sorted 佇列走訪到末端節點時仍有資料節點，則將剩餘的資料節點直接使用 list_splice_tail 合併。單寫完流程描述就覺得很複雜...
## 論文閱讀 Dude, is my code constant time?
時序攻擊 (Timing attack) 使用程式的執行時間，破解密碼系統以取得正確的系統密碼或金鑰。為了避免此問題的發生，可透過人工進行 code review 或利用自動檢查工具，確認程式碼的執行時間與輸入內容無相關性。
自動檢查工具常見使用靜態程式碼分析，確認程式的執行流程或記憶體存取狀態，然而此缺點為受限於需對硬體建立模型，否則難以準確估算程式的實際運算時間。本篇論文的作者提出使用預先定義好的測試數據，對程式碼實際運作時間分佈進行統計分析。簡單來說與其單純使用理論進行分析，不如直接用測試數據量測執行時間，透過統計學的方式確認是否滿足 constant time 。
論文作者提出的方法分為三大步驟
1. 建立測試資料
測試數據共分為`常數資料`與`亂數資料`兩大種類。前者通常會設計為可以使執行時間大幅變動的邊角案例 (corner case) ，測試過程中會將常數資料與亂數資料會被隨機且交錯的進行測試，降低受到其他並行行程 (concurrent process) 的影響。
2. 量測實際運作時間
精確的實際運作時間量測可透過 CPU 運算週期計數器或 MPU 的 timer 計數器實現，但須注意應將輸入資料的準備時間排除，而獲得的實際運作時間在進行統計前可先進行下列兩項後處理 (post-processing) ：
- Corpping ：當程式執行時間較長時，會因 CPU 分時多工的運算造成量測到的數據時間變長 (positive skew) ，需將該類型的數據額外處理或直接捨棄不納入統計。
- Higher-order preprocessing ：看不是很懂這個前置處理的用途，文中描述是參考 Higher-order DPA (Differential Power Analysis) attacks ，依據測試平台的硬體特性進行資料處理 (?) ，需要再閱讀相關的參考文獻確認。
3. 統計量測結果證明是否滿足 constant time
本篇論文使用『 `the two timing distributions are equal` 』 作為驗證程式是否滿足 constant time 的虛無假說 (null hypothesis) ，虛無假說是一種統計學上進行假說檢定 (hypothesis testing) 的假說種類，而假說檢定是推論統計中用於檢定現有數據是否足以支持特定假設的方法。
虛無假說的內容為研究者想要證明的對象，虛無假說的對立面即為對立假說 (alternative hypothesis) ，當統計結果顯示虛無假說不成立時，可證明研究者的論點是成立的。
以維基百科中的例子來說，在刑事訴訟法中第154條第一項規定『被告未經審判證明有罪確定前、推定其為無罪』，檢察官必須要提出足夠的證據去證明被告的確有罪。這個情境下對檢察官來說，被告無罪的假設即為虛無假說、被告有罪的假設即為對立假說。(路過的法律人表示：民事訴訟中舉證之所在、敗訴之所在...)
> [刑事訴訟法 §154](https://law.moj.gov.tw/LawClass/LawSingle.aspx?pcode=C0010001&flno=154)
> [假說檢定 - Wikipedia](https://zh.wikipedia.org/zh-tw/%E5%81%87%E8%AA%AA%E6%AA%A2%E5%AE%9A)
對於實驗結果使用到 Cumulative Distribution Function (CDF) 進行分析，其在維基百科的中文名稱為累積分布函數或機率分布函數，簡稱為分佈函數。其函數的定義為取一隨機變數數值 x ，其小於 X 的機率即為分佈函數。乍看之下與 Percentile Rank (俗稱 PR 值）很像，但兩者並不全然相同， PR 值是對具體數值`統計總量`，而 CDF 指的是該取樣某一數值時，得到小於等於該數值的`機率`。
以一個班級的學生數學成績作為例子，分數 87 分的 PR 值假設為 90% ，代表該班級總共有 90% 的學生分數小於等於 87 分；而 CDF 則代表在該班級進行抽樣，抽到的小於或等於87分的機率值為 0.9 。
論文的測試實驗程式碼應用功能有 `memcmp` 、 `AES128實作` 與 `Curve25519計算` 共三種，確認其提出的檢查工具 dudect 可正確判斷該程式碼的運算時間是否為 constant time 。
本篇論文的 discussion 提到幾個重點值得省思：
1. 由於提出的手法量測實際運算時間進行分析，故當平台更換硬體配置或軟體更新後，需重新執行運算時間量測與統計。
2. 測試資料的選用是能否偵測到程式為常數時間的關鍵因素之一，本篇論文的方法強調透過亂數資料與常數資料即可有效的達到目標，不需額外花心思找到會觸發非常數執行時間的輸入資料。但如果知道程式的實作方式，便可更容易證明非常數時間的輸入資料。
3. 由於使用統計資料進行分析，並非有明確指標 (categorical assessment) 可以直接判斷是否為常數時間，測試 N 次得到無法證明虛無假說的結果，不代表第 N+1 次的測試也會有相同結果。如同在 Differential power analysis, DPA 攻擊中需要一定數量 (security level) 的測試次數才會獲取到所需的資訊。
4. 統計結果僅代表趨勢，若顯示程式執行並非常數時間，並不代表該程式就一定受到時序攻擊的威脅。
5. 統計結果比起單純的 yes/no 結論更有說服力。
## Perf
### perf stat
`perf stat` 命令用於統計目標程式的性能分析，支援多次執行針對特定或一系列的 event 進行統計分析。依照 [Linux 效能分析工具： Perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 練習 perf 使用方式時，發現對下列範例程式執行 perf stat 的結果不太一樣。
```c
static char array[10000][10000];
int main (void){
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[j][i]++;
return 0;
}
```
在自己電腦上執行的統計結果多了 cpu_core 與 cpu_atom 字眼，經過查詢後得知 Intel 在第 12 代處理器導入 [異質運算 (Heterogeneous Computing)](https://en.wikipedia.org/wiki/Alder_Lake) 架構， CPU 會同時具備高運算能力的 performance core(cpu_core) 與高效能的 efficiency core(cpu_atom) 兩種核，此電腦搭載的 i3-1215U 處理器有 2 個 performance core 和 4 個 efficiency core ， perf 在進行效能分析時會將兩種核納入統計。
```shell
$ sudo perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./p_test
Performance counter stats for './p_test' (5 runs):
163,3767 cpu_core/cache-misses/ # 90.48% of all cache refs ( +- 0.27% ) (97.68%)
154,4886 cpu_atom/cache-misses/ # 85.55% of all cache refs ( +- 41.07% ) (2.32%)
180,5732 cpu_core/cache-references/ ( +- 0.15% ) (97.68%)
179,0624 cpu_atom/cache-references/ ( +- 41.01% ) (2.32%)
24,8918,0934 cpu_core/instructions/ # 3.23 insn per cycle ( +- 0.04% ) (97.68%)
13,8742,2291 cpu_atom/instructions/ # 1.80 insn per cycle ( +- 40.83% ) (2.32%)
7,7072,8951 cpu_core/cycles/ ( +- 0.20% ) (97.68%)
3,4847,1303 cpu_atom/cycles/ ( +- 40.83% ) (2.32%)
0.17921 +- 0.00138 seconds time elapsed ( +- 0.77% )
```
最左端的數字即為在該核發生的分析項目**平均**次數，中間為執行過程中發生分析項目的**平均**比例，由於是多次執行同個程式進行統計，故括號中的 +- 數值代表標準差，而最右邊的則是代表在不同類型的核上發生的佔比。
### perf record & perf report
有別於 `perf stat` 針對程式碼整體的 event 進行分析， `perf record` 與 `perf report` 可針對函式級別進行 event 統計，進行更精細的效能分析與調整， `perf record` 執行後會於該資料夾下產生 `perf.data` 儲存分析結果。如要針對特定的 event 進行分析，可使用 `-e` 選項達成，以 cache miss event 為例，透過下列命令流程可得知程式執行過程，在 main 函式中發生的 cache miss 佔了多少百分比。
```shell
$ sudo perf record -e cache-misses ./p_test
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.072 MB perf.data (916 samples) ]
$ sudo perf report
Samples: 916 of event 'cpu_core/cache-misses/', Event count (approx.): 3671350
Overhead Command Shared Object Symbol
47.22% p_test p_test [.] main
8.85% p_test [kernel.kallsyms] [k] _raw_spin_lock
5.89% p_test [kernel.kallsyms] [k] cgroup_rstat_updated
4.64% p_test [kernel.kallsyms] [k] blk_cgroup_congested
4.52% p_test [kernel.kallsyms] [k] __pte_offset_map_lock
4.39% p_test [kernel.kallsyms] [k] wp_page_copy
3.08% p_test [kernel.kallsyms] [k] __rcu_read_lock
2.11% p_test [kernel.kallsyms] [k] charge_memcg
1.94% p_test [kernel.kallsyms] [k] __free_one_page
...
```
從上述執行結果可觀查到， samples 數量與 Event count 數量並不相等。主要的[原因](https://perf.wiki.kernel.org/index.php/Tutorial#Sampling_with_perf_record)為此處的 samples 是依據寫入 perf.data 的資料量，與 event 量測所獲得的最小 sample 資料大小估算獲得。實際 event 發生次數應參考 perf report 中的 `Event count` 資訊。
perf 使用的取樣機制共有兩種：
1. time based (default)
依據設定每隔特定時間取樣，系統默認的取樣頻率為 1,000Hz ，可使用 `-F` 命令調整取樣頻率，最大頻率可參照 `/proc/sys/kernel/perf_event_max_sample_rate` 的設定。請注意，若設定過低有可能導致獲得的 event 數量低於實際數量的情況。
2. event based
取樣週期 (period) 代表的是共累積發生特定次數的 event ，每個目標 event 具備一個計數器，每當 event 發生時，該計數器會進行累加直到溢位，並紀錄為一次 sample 。
將範例程式改寫如下，新增 foo 與 add 兩個函式組成，並使用 perf record 觀察 cach miss 的情形。
```c
static char array[10000][10000];
void add(void) {
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[j][i] += 1;
}
void foo(void) {
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[j][i]++;
add();
}
int main (void) {
foo();
return 0;
}
```
從 perf report 輸出結果，可看到程式分別在 core 與 atom 處理器上進行運算，並可從結果上觀察到 add 與 foo 函式運算過程中遇到 cache miss 佔了多少百分比，請注意此處的 overhead 計算方式，並不包含呼叫的子函式。
```shell
$ sudo perf record -e cache-misses ./p_test
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.107 MB perf.data (1681 samples) ]
$ sudo perf report
Samples: 1K of event 'cpu_core/cache-misses/', Event count (approx.): 5203789
Overhead Command Shared Object Symbol
33.29% p_test p_test [.] add
33.26% p_test p_test [.] foo
5.03% p_test [kernel.kallsyms] [k] _raw_spin_lock
3.26% p_test [kernel.kallsyms] [k] wp_page_copy
2.69% p_test [kernel.kallsyms] [k] cgroup_rstat_updated
2.60% p_test [kernel.kallsyms] [k] __pte_offset_map_lock
2.47% p_test [kernel.kallsyms] [k] blk_cgroup_congested
...
Samples: 42 of event 'cpu_atom/cache-misses/', Event count (approx.): 562917
Overhead Command Shared Object Symbol
50.47% p_test [kernel.kallsyms] [k] clear_page_erms
29.97% p_test p_test [.] add
10.50% p_test p_test [.] foo
4.82% p_test [kernel.kallsyms] [k] consume_stock
2.95% p_test [kernel.kallsyms] [k] wp_page_copy
1.21% p_test [kernel.kallsyms] [k] blk_cgroup_congested
0.07% p_test [kernel.kallsyms] [k] __get_user_8
0.00% p_test [kernel.kallsyms] [k] perf_ctx_enable
```
### Children Overhead & Call-graph
若想要觀察子函式呼叫情形，可在執行 perf record 時使用 `-g` 命令，將記錄程式執行期間的呼叫圖 (call-graph) 資訊。透過 perf report 的輸出，我們可以觀察到在 foo 函式中， add 函式被呼叫的情況。值得注意的是，此處的 overhead 資訊被分為兩個部份：self 與 children ，且 children 的總和大於 100% 。這是因為 children overhead 包含了函式本身 (self) 與所有被呼叫的子函式的 overhead 總和。以 foo 函式為例，其自身的 overhead 為 33.06% ，而 add 函式的 overhead 為 33.37% 。將兩者相加即可得到 foo 函式的 children overhead 。這樣的資訊有助於我們識別哪個函式的 overhead 最為突出。
```shell
$ sudo perf record -g -e cache-misses ./p_test
[sudo] password for booleanii:
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.203 MB perf.data (1681 samples) ]
$ sudo perf report
Samples: 1K of event 'cpu_core/cache-misses/', Event count (approx.): 5360154
Children Self Command Shared Object Symbol
+ 96.36% 0.00% p_test libc.so.6 [.] __libc_start_call_main
+ 96.36% 0.00% p_test p_test [.] main
+ 96.36% 33.06% p_test p_test [.] foo
- 33.45% 33.37% p_test p_test [.] add
33.37% __libc_start_call_main
main
foo
add
+ 29.89% 1.11% p_test [kernel.kallsyms] [k] asm_exc_page_fault
+ 28.79% 0.00% p_test [kernel.kallsyms] [k] exc_page_fault
+ 28.79% 0.00% p_test [kernel.kallsyms] [k] do_user_addr_fault
+ 28.75% 0.00% p_test [kernel.kallsyms] [k] handle_mm_fault
+ 28.75% 0.00% p_test [kernel.kallsyms] [k] __handle_mm_fault
+ 28.75% 0.00% p_test [kernel.kallsyms] [k] handle_pte_fault
...
```
我們再修改了下範例程式碼，觀察當一個函式於多個函式中呼叫時，在呼叫圖中是如何被呈現的。修改後的程式碼在 foo 與 main 函式中，各呼叫一次 add 函式。
```c
static char array[10000][10000];
void add(void) {
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[j][i] += 1;
}
void foo(void) {
int i, j;
for (i = 0; i < 10000; i++)
for (j = 0; j < 10000; j++)
array[j][i]++;
add();
}
int main (void) {
foo();
add();
return 0;
}
```
```shell
$ sudo perf record -g -e cache-misses ./p_test
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.268 MB perf.data (2420 samples) ]
$ sudo perf report
Smples: 2K of event 'cpu_core/cache-misses/', Event count (approx.): 7404379
Children Self Comman Shared Object Symbol
+ 97.53% 0.00% p_test libc.so.6 [.] __libc_start_call_main
+ 97.53% 0.00% p_test p_test [.] main
+ 72.95% 25.04% p_test p_test [.] foo
- 49.67% 49.43% p_test p_test [.] add
49.43% __libc_start_call_main
- main
- 24.96% foo
add
24.47% add
+ 22.70% 0.64% p_test [kernel.kallsyms] [k] asm_exc_page_fault
+ 22.06% 0.00% p_test [kernel.kallsyms] [k] exc_page_fault
+ 22.06% 0.00% p_test [kernel.kallsyms] [k] do_user_addr_fault
+ 22.06% 0.03% p_test [kernel.kallsyms] [k] handle_mm_fault
+ 22.03% 0.00% p_test [kernel.kallsyms] [k] __handle_mm_fault
+ 22.03% 0.00% p_test [kernel.kallsyms] [k] handle_pte_fault
...
```
>[Perf Tutorial](https://perf.wiki.kernel.org/index.php/Tutorial)
>[Perf 中文介紹](https://zh-blog.logan.tw/2019/07/10/analyze-program-performance-with-perf-events/)
>[Perf Graph](https://zh-blog.logan.tw/2019/10/06/intro-to-perf-events-and-call-graph/)
Sign in with Wallet
Connect another wallet