# 2020q3 Homework1 (lab0)
contributed by < [WeiCheng14159](https://github.com/WeiCheng14159) >
###### tags: `sysprog2020`
## Outline
[TOC]
## 環境
```shell
$ uname -a
Linux 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
```
## 作業要求
在 ``queue.[c/h]`` 中完成以下實作
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增==順序來排序鏈結串列的元素
## 實作流程
### queue.h
* 在 `queue.h` 中增加的 `list_ele_t *tail`, `unsigned int size;` 使得 `q_size()` , `q_insert_tail()` 能在 $O(1)$ 時間內完成
* 加上 `unsigned int size` 的同時也限制了queue的容量
* queue 所需的記憶體空間增加為 `2 x sizeof(list_ele_t*) + sizeof(unsigned int)`
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* Linked list of elements */
int size; /* size of the queue*/
} queue_t;
```
### queue.c
* **q_new**
* 操作 `*q` 之前，先確認 `malloc` 是否成功
* `q->size` 初始值為0
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = q->tail = NULL;
q->size = 0;
return q;
}
```
* **q_free**
* 利用 `tmp` 指標路過每一個節點，並釋放記憶體
```cpp
void q_free(queue_t *q)
{
if (!q)
return;
while (q->head) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
* **q_insert_head**
* 若 `q` 為 `NULL` 則不能插入任何節點
* `strlen()` 函數計算 `c-style string` 的長度，注意此長度不包含最後的 `\0`
* 若任意一個 `malloc` 無法取得記憶體，則應釋放已經持有之記憶體
* 參照 CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 的建議使用 `strlcpy` 取代 `strcpy` 以避免 buffer overflow 的問題
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q || q->size == INT_MAX)
return false;
// strlen calculates the lenght of C string
//(without including the terminating null character itself).
int strLen = strlen(s) + 1;
list_ele_t *newHead = (list_ele_t *) malloc(sizeof(list_ele_t));
char *val = (char *) malloc(sizeof(char) * strLen);
// either one of malloc fail to allocate memory
if (!newHead || !val) {
free(newHead);
free(val);
return false;
}
strlcpy(val, s, strLen);
newHead->value = val;
newHead->next = q->head;
q->head = newHead;
if (q->size == 0) { // empty queue
q->tail = newHead;
}
q->size++;
return true;
}
```
* **q_insert_tail**
* 同上
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
if (!q || q->size == INT_MAX)
return false;
int strLen = strlen(s) + 1;
list_ele_t *newTail = (list_ele_t *) malloc(sizeof(list_ele_t));
char *val = (char *) malloc(sizeof(char) * strLen);
if (!newTail || !val) {
free(newTail);
free(val);
return false;
}
strlcpy(val, s, strLen);
newTail->value = val;
newTail->next = NULL;
if (q->size == 0) { // empty queue
q->head = newTail;
} else {
q->tail->next = newTail;
}
q->tail = newTail;
q->size++;
return true;
}
```
* **q_remove_head**
* 需要計算 `strlcpy` 實際要拷貝多大的記憶體
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !sp || !q->head)
return false;
list_ele_t *rmElem = q->head;
int strLen = strlen(rmElem->value) + 1;
size_t realBufSize = bufsize > strLen ? strLen : bufsize;
strlcpy(sp, rmElem->value, realBufSize);
q->head = q->head->next;
q->size--;
free(rmElem->value);
free(rmElem);
return true;
}
```
* **q_size**
* 在 $O(1)$ 時間回傳queue的大小
```cpp
int q_size(queue_t *q)
{
if (!q)
return 0;
else
return q->size;
}
```
* **q_reverse**
* 標準的 `linked list` 反轉
```cpp
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *tmp = q->head;
list_ele_t *prev = NULL;
while (q->head != NULL) {
list_ele_t *next = q->head->next;
q->head->next = prev;
prev = q->head;
q->head = next;
}
q->head = q->tail;
q->tail = tmp;
}
```
* **q_sort**
* 參考課程提供的連結 [Linked LIst Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
* 使用 Merge sort 因為時間複雜度最佳
* `list_cmp` 決定兩個list的順序
```cpp
inline bool list_cmp(list_ele_t *l1, list_ele_t *l2)
{
// assume *l1 and *l2 aren't NULL
return (strcmp(l1->value, l2->value) >= 0) ? false : true;
}
```
* `merge` 依據兩個list的內容合併為一個list （舊的 recursive 版本）
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
if (list_cmp(l1, l2)) { // compare 2 lists
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
```
* `merge` [更] 兩個list的內容合併為一個list（新的 iterative 版本）
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *tmp, *head;
if (list_cmp(l1, l2)) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
head = tmp;
while (l1 && l2) {
if (list_cmp(l1, l2)) { // compare 2 lists
tmp->next = l1;
l1 = l1->next;
} else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if (!l1)
tmp->next = l2;
if (!l2)
tmp->next = l1;
return head;
}
```
* `merge_sort` 回傳排序好的指針
```cpp
list_ele_t *merge_sort(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
// sort each list
list_ele_t *l1 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
// merge sorted list l1 and l2
return merge(l1, l2);
}
```
* 需要額外處理tail pointer
```cpp
void q_sort(queue_t *q)
{
if (!q || !q->head || !q->head->next)
return;
q->head = merge_sort(q->head);
list_ele_t *tmp = q->head;
while (tmp->next) {
tmp = tmp->next;
}
q->tail = tmp;
}
```
## Debug
* 遇到的問題： `make test` 後第15個test case有問題
* `+++ TESTING trace trace-15-perf: # Test performance of insert_tail, size, reverse, and sort`
* 處理流程
* 進入 `./traces` 資料夾找到 `trace-15-perf.cmd` 的測試指令如下
```
# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000
```
* `make clean` 後重新編譯，利用 `make SANITIZER=1` 開啟記憶體檢測再執行測試
```
==9115==ERROR: AddressSanitizer: stack-overflow on address 0x7ffd01123ff8 (pc 0x7f908757fe6f bp 0x7ffd01124860 sp 0x7ffd01123fc0 T0)
```
* 結果得知 `queue.c` 的第 206 行有 stack-overflow 的問題，估計是遞迴函數 `list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)` 被遞迴呼叫所造成
* 參考 [Merge two list iteratively](https://www.geeksforgeeks.org/merge-two-sorted-lists-place/) 實做 iteratively merge two list 的方法，結果如下：
* 如果允許使用額外的記憶體，可以使用一個 `dummy node` 使程式碼更簡潔，但本題要求 `in-place sorting` 故不適用
* 不使用 `dummy node` 則程式較冗長
```cpp
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *tmp, *head;
if (list_cmp(l1, l2)) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
head = tmp;
while (l1 && l2) {
if (list_cmp(l1, l2)) { // compare 2 lists
tmp->next = l1;
l1 = l1->next;
} else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}
if (!l1)
tmp->next = l2;
if (!l2)
tmp->next = l1;
return head;
}
```
* `make test` 全數通過且 `iterative` 版本的 `merge` 函式已更新
## Valgrind 實驗
* 實驗：利用 `Massif` 視覺化指令檔 `trace-perf.cmd` 的記憶體使用量
* 其中 `traces/trace-perf.cmd` 的指令如下
```
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
option fail 0
option malloc 0
new
ih ABC 10000
sort
reverse
sort
free
new
ih ABC 50000
sort
reverse
sort
free
new
ih ABC 100000
sort
reverse
sort
free
```
* 環境設定：依照官方建議安裝 [massif-visualizer](https://github.com/KDE/massif-visualizer) `$ sudo apt install massif-visualizer `
* 執行測試：`valgrind --tool=massif ./qtest < traces/trace-perf.cmd`
* 記憶體佔用情形 
* 共有三個記憶體佔用峰值，分別是 986.5 KiB, 4.8 MiB, 9.5 MiB
* 分別對應到10000/50000/100000個 `list_ele_t`，其中每一個 element 的內容都是 `ABC`
* 分析記憶體佔用如下：
* `queue_t` 佔用兩個 `pointer` 跟一個 `int` 共20 bytes
* `list_ele_t` 佔用一個 `char*` 跟一個 `list_ele_t*` 共16 bytes
* 每個`ABC` c-style string 佔用4 bytes，共有10000/50000/100000個
* 10000個 `list_ele_t` 會佔用20+(16+4)*10000 bytes ~= 200KiB
* 50000個 `list_ele_t` 會佔用20+(16+4)*50000 bytes ~= 1MiB
* 100000個 `list_ele_t` 會佔用20+(16+4)*100000 bytes ~= 2MiB
* 估計值與實際值有不小的差距，還在找原因
## branch 最佳化實驗
* 起因：參考[GNU/Linux 開發工具共筆](https://hackmd.io/@sysprog/gnu-linux-dev/)的perf效能分析工具，想要了解這個程式的提昇空間
* 使用 `traces/trace-perf.cmd` 測試 queue 的排序效能，指令檔如下
```
option fail 0
option malloc 0
new
ih RAND 100000
sort
free
```
* 利用 `perf record` 紀錄 `branch-misses` 和 `branch-instructions` 的發生次數
* `$ perf record -e branch-misses:u,branch-instructions:u ./qtest < traces/trace-perf.cmd`
* 結果：
* `branch-misses` 前五名
| | branch-misses |
|--------|-----------------------------|
| 50.04% | merge |
| 14.44% | __strcmp_sse2_unaligned |
| 8.34% | q_insert_head |
| 4.22% | __random |
| 2.97% | _IO_default_xsputn |
* `branch-instructions`前五名
| | branch-instructions |
|--------|-----------------------------|
| 12.81% | merge |
| 11.38% | fill_rand_string |
| 9.49% | __random |
| 8.86% | __strcmp_sse2_unaligned |
| 6.47% | __random_r |
* 分析：發現 linked list 的操作 branch 的機會本來就很多不像 loop 可以 unroll 減少 branch misses 故找不到最佳化切入點作罷。想了解 `__strcmp_sse2_unaligned` 函式有沒有最佳化的空間（因為看到 `unaligned` 感覺可以做更好）但是看不懂 `x86 assembly` 故作罷。
## 論文研讀
`Dude, is my code constant time?` 這篇論文中藉由偵測執行時間，來獲取程式的時間複雜度資訊。其中運用處理器洩漏出來的資訊，反向推斷程式執行的狀態之研究領域被稱為 `side-channel domain` 。近期較出名的相關研究有 `Meltdown` `Spectrum` 等漏洞，是利用處理器硬體架構的特性作為攻擊的手段，是為 `side-channel attack` 。
本篇論文的貢獻是，將上述之特性運用到程式時間複雜度之量測上。具體之作法是給程式兩個不同類型的輸入資料（i.e. fix-vs-random 測試），並觀察給定不同的輸入資料，所造成的執行時間分佈在統計上是否相同。以下是詳細的步驟：
* 步驟一：量測時間
* 運用 `fix-vs-random` 產生兩種測試資料，顧名思義，第一種資料皆是常數，第二種資料是亂數
* 藉由處理器內部的暫存器得知執行時間，確切的程式碼可在 `dudect/cpucycles.h` 找到
```c=1
#include <stdint.h>
// http://www.intel.com/content/www/us/en/embedded/training/ia-32-ia-64-benchmark-code-execution-paper.html
static inline int64_t cpucycles(void)
{
#if defined(__i386__) || defined(__x86_64__)
unsigned int hi, lo;
__asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
return ((int64_t) lo) | (((int64_t) hi) << 32);
#else
#error Unsupported Architecture
#endif
}
```
* 根據連結 [How to Benchmark Code Execution Times on Intel® IA-32 and IA-64 Instruction Set Architectures](https://www.intel.com/content/www/us/en/embedded/training/ia-32-ia-64-benchmark-code-execution-paper.html) 發現在 x86 或 x86_64 架構中，程式使用 `rdtsc` 指令讀取執行的 cycle 數並不準確
* 問題描述如下：Intel CPU 每一個核心有個 timestamp counter 來計算執行的 cycle 數目，並可使用 `RDTSCP (Read Time-Stamp Counter and Processor ID IA assembly instruction)` 和 `RDTSC` 指令來存取執行的 cycle 數目
* 乍看之下，如按照以下步驟，我們應該可以得到準確的執行時間
* `disable preemption on our CPU`
* `disable hard interrupts on our CPU`
* 讀取 `timestamp counter`
* 執行待測的程式
* 再次讀取 `timestamp counter`
* `enable preemption on our CPU`
* `enable hard interrupts on our CPU`
* 將兩個 `cycle count` 相減得到佔用 `cycle` 數
* Intel 指出這樣的計算方式並不能夠得到正確的執行時間，因為現今多數的處理器都支援亂序執行 (OOOE) 來實現 `latency hiding` 故不能保證上述的指令在 CPU 中是按照順序執行的，解決方法是在讀取 `RDTSC` 暫存器之前加入序列化指令 (`serializing instruction`) 告訴 CPU 接下來的指令必須嚴格按照順序執行。另外，還有 `Register Overwriting` 的問題（此處不贅述）
* Intel 建議正確的時間測量程式應該如此撰寫：
```c=1
asm volatile ("CPUID\n\t"
"RDTSC\n\t"
"mov %%edx, %0\n\t"
"mov %%eax, %1\n\t": "=r" (cycles_high), "=r" (cycles_low)::
"%rax", "%rbx", "%rcx", "%rdx");
/***********************************/
/*call the function to measure here*/
/***********************************/
asm volatile("RDTSCP\n\t"
"mov %%edx, %0\n\t"
"mov %%eax, %1\n\t"
"CPUID\n\t": "=r" (cycles_high1), "=r" (cycles_low1)::
"%rax", "%rbx", "%rcx", "%rdx");
```
* 其中 `CPUID` 是序列化指令，`RDTSCP` 是讀取 `timestamp counter` 的指令
* Intel 建議的時間測量方法跟本篇論文的測量方法略有不同，本篇論文沒有考慮 OOOE 對時間測量的影響，需要實際測試一下 Intel 建議的方法對時間複雜度的判定會不會有影響(i.e. 在高負載的 CPU 上執行會不會影響 `dudect` 程式判定時間複雜度的結果)
* 此外，根據以下 `dudect/constant.c` 中的程式碼，`cpucycles()` 函式讀取 `timestamp register` 之前並沒有按照 Intel 的建議關閉 `preemption` 和 `hard interrupt` ，作業系統層級的時間影響還要再多做測試
```c=55
void measure(int64_t *before_ticks,
int64_t *after_ticks,
uint8_t *input_data,
int mode)
{
assert(mode == test_insert_tail || mode == test_size);
if (mode == test_insert_tail) {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
dut_free();
}
} else {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
before_ticks[i] = cpucycles();
dut_size(1);
after_ticks[i] = cpucycles();
dut_free();
}
}
}
```
* 步驟二：資料後處理
* 執行時間的判定會被外部干擾所影響（i.e. `context switch` ）故需要捨棄不合理的資料，捨棄的標準需要手動設定 `(p-th percentile)`
* 步驟三：統計上的判定
* `Hypothesis Testing` 簡介：
* `Null hypothesis (H0)` 是我們想要測定的假說
* `Alternative hypothesis (H1)` 是 `H0` 的反面
* 結果的判定：
* `Reject Null Hypothesis` 代表我們在統計上有足夠的證據，證明 `H0` 是錯的，故 `H1` 是對的
* `Fail to reject Null Hypothesis` 代表在統計上==沒有==足夠的證據，證明 `H0` 是錯的
* 在本論文中 `Welch’s t-test` 的運用如下：
* 定義：
* $\mu_1$：`class 1` 真正的執行時間的平均值（未知）
* $\mu_2$：`class 2` 真正的執行時間的平均值（未知）
* $\sigma_1$：`class 1` 採樣的執行時間的標準差（已知）
* $\sigma_2$：`class 2` 採樣的執行時間的標準差（已知）
* $n_1$：`class 1` 的樣本數（已知）
* $n_2$：`class 2` 的樣本數（已知）
* $\bar x_1$：`class 1` 採樣的的執行時間的平均值（已知）
* $\bar x_2$：`class 2` 採樣的的執行時間的平均值（已知）
* $H_0$：$\mu_1 - \mu_2 = 0$ 假設`class 1` 和`class 2` 的平均執行時間相等，亦為 ==『兩個 `class` 的執行時間分佈是相同的』==
* $H_1$：$\mu_1 - \mu_2 \neq 0$ 假設`class 1` 和`class 2` 的平均執行時間並不相等，亦為 ==『兩個 `class` 的執行時間分佈是不同的』==
* 計算檢定統計量 $t = \frac{\bar x_1 - \bar x_2}{\sqrt{\frac{\sigma_1^2}{n_1}+ \frac{\sigma_2^2}{n_2}}}$
* 若 $|t| \gt z_{\frac{\alpha}{2}}$ 則 `reject` $H_0$ 進而得到 $\mu_1 \neq \mu_2$ ，代表以不同 `class` 為輸入的執行時間的平均在統計上是不同的
* 若 $|t| \leq z_{\frac{\alpha}{2}}$ 則 無法 `reject` $H_0$ 推得 $\mu_1$ ==可能== 等於 $\mu_2$ ，在統計上無法判定
* $z_{\frac{\alpha}{2}}$ 之值在統計上要查表，論文中卻使用 `#define t_threshold_moderate 10` 來計算不知為何
* 檢定統計量的判定可以在 `static bool report(void)` 中找到
* 例如：`class 1` 為常數資料，`class 2` 為亂數資料。將兩種資料餵給程式，並計算多筆執行時間，帶入上述公式計算檢定統計量，如果可以 `reject` $H_0$ 則此程式的時間複雜度在統計上並不如其所宣稱的好，因為亂數輸入的時間複雜度和常數輸入的時間複雜度不相同，原因可能是亂數輸入觸發了程式中的某些執行路徑，導致時間複雜度增加
Sign in with Wallet
Connect another wallet