# 2020q1 Homework1 (lab0)
contributed by < `jeeeff` >
:::danger
Show me the code! 什麼都是假的，只有高品質的程式碼才是真的。
依據你的 [GitHub 提交動態](https://github.com/jeeeff/lab0-c/commits/master)，可發現你不是透過命令列 (自然就沒有 Git hooks) 來提交程式碼，這是錯誤的！請依循作業要求「重新」做過！
工程開發的「紀律」是本課程著重的素養之一，你可以想像 Google 或 Apple 公司的工程師總是便宜行事的模樣嗎？如果這些工程師缺乏紀律，你敢用他們做出來的手機嗎？
儘快改正！
:notes: jserv
:::
:::success
commit
>好，已經重新用好code了[name=柯玠甫]
:::
## 實驗環境
作業系統
```shell
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 18.04.4 LTS
Release: 18.04
Codename: bionic
```
編譯器
```shell
$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
Copyright (C) 2017 Free Software Foundation, Inc.
```
## 實做過程 - queue.c
### q_new
* 新增一個 Queue 的一些初始化設定，若 malloc 失敗要回傳 NULL
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
memset(q, 0, sizeof(queue_t));
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
* 釋放一個 Queue 佔用的記憶體
* 重複利用 q_remove_head 使程式收斂，更好維護
```clike=
void q_free(queue_t *q)
{
while(q_remove_head(q,NULL,0))
;
free(q);
}
```
### q_insert_head
* 從 head 插入，如果 str_val 的 malloc 失敗必須 free newh，不然測試資料 trace-11-malloc 和 trace-12-mallo 會出現錯誤：
```
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
--- trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-11-malloc 0/6
```
:::danger
文字訊息不要用圖片展現，改！
:notes: jserv
:::
:::success
commit
>好，已經改好了！[name=柯玠甫]
:::
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *str_val = malloc((strlen(s) + 1) * sizeof(char));
if (!str_val) {
free(newh);
return false;
}
memset(str_val, '\0', strlen(s) + 1);
strncpy(str_val, s ,strlen(s));
newh->value = str_val;
newh->next = q->head;
q->head = newh;
if (!q->tail)
q->tail = newh;
q->size++;
return true;
}
```
### q_insert_tail
* 和 q_insert_head 只插在指標指向的位置不一樣
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt)
return false;
char *str_val = malloc((strlen(s) + 1) * sizeof(char));
if (!str_val) {
free(newt);
return false;
}
memset(str_val, '\0', strlen(s) + 1);
strncpy(str_val, s ,strlen(s));
newt->value = str_val;
newt->next = NULL;
q->size++;
if (!q->head) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
return true;
}
```
### q_remove_head
* 將 head 的 value 放進 sp，並將 head 從 q 移除
* 因為 sp 有限制大小（bufsize），所以用 strncpy 而不是 strcpy
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || q->size == 0)
return false;
list_ele_t *node;
node = q->head;
if (sp != NULL) {
memset(sp, '\0', bufsize);
strncpy(sp, node->value, bufsize - 1);
}
q->head = q->head->next;
free(node->value);
free(node);
q->size--;
return true;
}
```
### q_size
* 作業要求 q_sort 須為 O(1)
```clike=
int q_size(queue_t *q)
{
if (!q)
return 0;
return q->size;
}
```
### q_reverse
* 將Linked list反轉
```clike=
void q_reverse(queue_t *q)
{
if (!q || q->size == 0)
return;
list_ele_t *t1, *t2;
q->tail = q->head;
t1 = q->head->next;
t2 = q->tail;
while (t1) {
q->head = t1;
t1 = t1->next;
q->head->next = t2;
t2 = q->head;
}
q->tail->next = NULL;
}
```
### q_sort
* 作業要求用 dictionary sort ，所以用strcmp製作
* 一開始沒注意到所以用 bubble sort ，後來為了達到 O(nlogn) 改用 merge sort ，但測試資料 trace-15-perf 一直不過，用 qtest 發現是卡在sort的部份：
```
cmd> option malloc 0
cmd> option malloc 0
cmd> option fail 0
cmd> option fail 0
cmd> new
cmd> new
q = []
cmd> ih dolphin 1000000
cmd> ih dolphin 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> it gelbic 1000000
cmd> it gelbic 1000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> size 1000
cmd> size 1000
Queue size = 2000000
q = [dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin dolphin ... ]
cmd> reverse
cmd> reverse
q = [gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic ... ]
cmd> size 1000
cmd> size 1000
Queue size = 2000000
q = [gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic gelbic ... ]
cmd> sort
cmd> sort
程式記憶體區段錯誤 (核心已傾印)
```
試了其他方法才知道是不能用遞迴，在下方 [Valgrind](https://hackmd.io/B25a_J2FTsGZG4zNYLAE0Q?view#Valgrind) 有比較詳細的修正過程
:::danger
何以有此推論？遞迴當然也能寫出高效能的程式碼。
推論需要有證據和分析。
:notes: jserv
:::
:::success
commit
>我用[ Dude, is my code constant time? ](https://eprint.iacr.org/2016/1123.pdf)嘗試看看！[name=柯玠甫]
>已經補上。[name=柯玠甫]
:::
```cpp
void q_sort(queue_t *q)
{
if (!q || q->size <= 1)
return;
q->head = mergeSortList(q->head);
list_ele_t *temp = q->head;
int i;
for (i = 1; i < q->size; i++)
temp = temp->next;
q->tail = temp;
}
```
### merge
```clike=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *tmp;
if (strcmp(l1->value, l2->value) < 0) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
list_ele_t *final = tmp;
while (l1 != NULL && l2 != NULL) {
if (strcmp(l1->value, l2->value) < 0) {
tmp->next = l1;
l1 = l1->next;
} else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
tmp->next = NULL;
}
if (l1)
tmp->next = l1;
if (l2)
tmp->next = l2;
return final;
}
```
### mergeSortList
```clike=
list_ele_t *mergeSortList(list_ele_t *head)
{
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
return merge(l1, l2);
}
```
## 實做過程 - queue.h
### struct
* 新增 size 變數，使 q_sort 達到 O(1)
```clike=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### merge
```clike=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2);
```
### mergeSortList
```clike=
list_ele_t *mergeSortList(list_ele_t *head);
```
## Valgrind
* 開發中遇到的問題：q_sort起初用了兩層遞迴，那時的 merge 副程式為
```clike=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
if (strcmp(l1->value, l2->value) < 0) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
```
於是用 Valgrind 檢測
```
$ make valgrind
```
可以發現 Stack 的空間不夠用，第15筆測資無法通過：
```
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==31439== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==31439== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==31439== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==31439== no stack segment
==31439==
==31439== Process terminating with default action of signal 11 (SIGSEGV)
==31439== Access not within mapped region at address 0x1FFE8010A8
==31439== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==31439== at 0x10CE3E: merge (queue.c:185)
==31439== If you believe this happened as a result of a stack
==31439== overflow in your program's main thread (unlikely but
==31439== possible), you can try to increase the size of the
==31439== main thread stack using the --main-stacksize= flag.
==31439== The main thread stack size used in this run was 8388608.
==31439== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
...
...
```
所以為了不呼叫太多次副程式，我將第二層的 recursive 改成 iterative ， merge 也就改成目前版本：
```clike=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
if (!l2)
return l1;
if (!l1)
return l2;
list_ele_t *tmp;
if (strcmp(l1->value, l2->value) < 0) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
list_ele_t *final = tmp;
while (l1 != NULL && l2 != NULL) {
if (strcmp(l1->value, l2->value) < 0) {
tmp->next = l1;
l1 = l1->next;
} else {
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
tmp->next = NULL;
}
if (l1)
tmp->next = l1;
if (l2)
tmp->next = l2;
return final;
}
```
然後再 **$ make valgrind** 一次，第15筆測資就能順利通過
```
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
--- trace-15-perf 6/6
```
## 實做過程 - massif-visualizer
安裝 massif 比較麻煩的地方是一直出現漏載檔案的警示，第一個是
```
CMake Error at CMakeLists.txt:6 (find_package):
Could not find a package configuration file provided by "ECM" (requested
version 0.0.9) with any of the following names:
ECMConfig.cmake
ecm-config.cmake
Add the installation prefix of "ECM" to CMAKE_PREFIX_PATH or set "ECM_DIR"
to a directory containing one of the above files. If "ECM" provides a
separate development package or SDK, be sure it has been installed.
-- Configuring incomplete, errors occurred!
See also "/home/awj1358/linux20/massif/build/CMakeFiles/CMakeOutput.log".
```
於是我上網找到載點
```
$ sudo apt-get install extra-cmake-modules
```
接著遇到第二個遺漏檔案的警示
```
CMake Error at CMakeLists.txt:22 (find_package):
Could not find a package configuration file provided by "Qt5" (requested
version 5.2.0) with any of the following names:
Qt5Config.cmake
qt5-config.cmake
Add the installation prefix of "Qt5" to CMAKE_PREFIX_PATH or set "Qt5_DIR"
to a directory containing one of the above files. If "Qt5" provides a
separate development package or SDK, be sure it has been installed.
-- Configuring incomplete, errors occurred!
See also "/home/awj1358/linux20/massif-visualizer/build/CMakeFiles/CMakeOutput.log".
```
而找到的載點是
```
$ sudo apt-get install qtbase5-dev
$ sudo apt-get install qtdeclarative5-dev
```
接著遇到第三次遺漏檔案的警示
```
CMake Error at /usr/lib/x86_64-linux-gnu/cmake/Qt5/Qt5Config.cmake:28 (find_package):
Could not find a package configuration file provided by "Qt5Svg" with any
of the following names:
Qt5SvgConfig.cmake
qt5svg-config.cmake
Add the installation prefix of "Qt5Svg" to CMAKE_PREFIX_PATH or set
"Qt5Svg_DIR" to a directory containing one of the above files. If "Qt5Svg"
provides a separate development package or SDK, be sure it has been
installed.
Call Stack (most recent call first):
CMakeLists.txt:22 (find_package)
-- Configuring incomplete, errors occurred!
See also "/home/awj1358/linux20/massif-visualizer/build/CMakeFiles/CMakeOutput.log".
```
找到的載點為
```
$ sudo apt install libqt5svg5-dev
```
然後遇到第四次檔案遺漏的警示
```
CMake Error at /usr/lib/x86_64-linux-gnu/cmake/Qt5/Qt5Config.cmake:28 (find_package):
Could not find a package configuration file provided by "Qt5XmlPatterns"
with any of the following names:
Qt5XmlPatternsConfig.cmake
qt5xmlpatterns-config.cmake
Add the installation prefix of "Qt5XmlPatterns" to CMAKE_PREFIX_PATH or set
"Qt5XmlPatterns_DIR" to a directory containing one of the above files. If
"Qt5XmlPatterns" provides a separate development package or SDK, be sure it
has been installed.
Call Stack (most recent call first):
CMakeLists.txt:22 (find_package)
-- Configuring incomplete, errors occurred!
See also "/home/awj1358/linux20/massif-visualizer/build/CMakeFiles/CMakeOutput.log".
```
這次找到的是工具，讓我們直接找到終端機警示中找不到的檔案，首先輸入
```
$ sudo apt install apt-file
$ sudo apt update
```
接著就可以直接找出 Qt5XmlPatternsConfig.cmake 的位置
```
$ apt-file search Qt5XmlPatternsConfig.cmake
libqt5xmlpatterns5-dev: /usr/lib/x86_64-linux-gnu/cmake/Qt5XmlPatterns/Qt5XmlPatternsConfig.cmake
```
根據網頁 [[SOLVED] Compilation Fails for Debian 10](https://forum.freecadweb.org/viewtopic.php?t=37036) 我下載了 libqt5xmlpatterns5-dev ，然後再 **$ cmake . .** 就能一次看到多個找不到的檔案
```
-- Could NOT find KF5Archive (missing: KF5Archive_DIR)
-- Could NOT find KF5Archive: found neither KF5ArchiveConfig.cmake nor kf5archive-config.cmake
-- Could NOT find KF5Config (missing: KF5Config_DIR)
-- Could NOT find KF5Config: found neither KF5ConfigConfig.cmake nor kf5config-config.cmake
-- Could NOT find KF5CoreAddons (missing: KF5CoreAddons_DIR)
-- Could NOT find KF5CoreAddons: found neither KF5CoreAddonsConfig.cmake nor kf5coreaddons-config.cmake
-- Could NOT find KF5Parts (missing: KF5Parts_DIR)
-- Could NOT find KF5Parts: found neither KF5PartsConfig.cmake nor kf5parts-config.cmake
-- Could NOT find KF5KIO (missing: KF5KIO_DIR)
-- Could NOT find KF5KIO: found neither KF5KIOConfig.cmake nor kf5kio-config.cmake
-- Could NOT find KF5I18n (missing: KF5I18n_DIR)
-- Could NOT find KF5I18n: found neither KF5I18nConfig.cmake nor kf5i18n-config.cmake
CMake Error at /usr/share/cmake-3.10/Modules/FindPackageHandleStandardArgs.cmake:137 (message):
Could NOT find KF5 (missing: Archive Config CoreAddons Parts KIO I18n)
Call Stack (most recent call first):
/usr/share/cmake-3.10/Modules/FindPackageHandleStandardArgs.cmake:378 (_FPHSA_FAILURE_MESSAGE)
/usr/share/ECM/find-modules/FindKF5.cmake:110 (find_package_handle_standard_args)
CMakeLists.txt:31 (find_package)
-- Configuring incomplete, errors occurred!
See also "/home/awj1358/linux20/massif-visualizer/build/CMakeFiles/CMakeOutput.log".
```
然而目前還沒找到下載點，可能未來找到才能使用massif
## Dude, is my code constant time?
### Simulation
* 統計運算時間
* Classes def. : 使用 fix-vs-random 兩種輸入（測試資料）給 CPU
* Cycle counters : 計算經歷的 cycle 數目得到執行時間
* Environmental cond. : 為了降低環境影響，輸入資料的工作優先於時間的計算
* 統計資料的後製
* Cropping : 將因系統因素導致的不合理統計資料刪除
* Higher-order preprocessing : 採取一些預處理（preprocessing）
* 證明兩條線不同
* t-test : 利用 Welch’s t-test
* Non-parametric tests : 例如使用 Kolmogorov-Smirnov
* Result analysis
* 在 clock cycles-cdf 圖中，若兩線呈 overlapped ，則完全沒有 timing leakage ，為 constant time ，例
* 若 clock cycles-cdf 圖兩條線不同，則代表偵測到 timing leakage ，並代表演算法非 constant time ，例
### Student's t-distribution
* 雙樣本檢驗是 Student's t-distribution 的一種，當兩母體 Variant 相等才稱之，否則有時稱 Welch’s t-test
### Welch’s t-test
* t = $\dfrac{\bar{X_1}-\bar{X_2}}{\sqrt{\dfrac{s_1^2}{N_1}+\dfrac{s_2^2}{N_2}}}$
* v =~ $\dfrac{(\dfrac{s_1^2}{N_1}+\dfrac{s_2^2}{N_2})^2}{\dfrac{s_1^4}{N_1^2v_1}+\dfrac{s_2^4}{N_2^2v_2}}$
* $\bar{X_i}$ : Sample mean
* $s_i$ : Sample standard deviation
* $N_i$ : Sample size
* $v_i$ : degrees of freedem
* i = {1,2}
* 當 t 越小（趨近0），代表 timing leakage 越小，程式越接近 constant time
### dudect 的實做
* 在 constant.c 的底端 measure 副程式的 mode 變數會選擇要測試 insert_tail 或 insert_head ，他們分別都會將使用 cpucycles() 求出執行時間的始末，並以 cycle 為時間單位儲存在 before_ticks[i] 和 after_ticks[i]
```clike=
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++) {
...
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
...
}
} else {
for (size_t i = drop_size; i < number_measurements - drop_size; i++) {
...
before_ticks[i] = cpucycles();
dut_size(1);
after_ticks[i] = cpucycles();
...
}
}
}
```
#### 統計運算時間
* 接著在 fixture.c 前段 differentiate 將執行時間儲存到 exec_times[i]
```clike=
static void differentiate(int64_t *exec_times,
int64_t *before_ticks,
int64_t *after_ticks)
{
for (size_t i = 0; i < number_measurements; i++) {
exec_times[i] = after_ticks[i] - before_ticks[i];
}
}
```
#### 統計資料的後製
* 在 fixture.c 的副程式 update_statistics 會篩選掉不必要的資料，這些資料是 overflowed 或 dropped 的，而合格的資料會藉由 t_push 儲存到 struct t_ctx 的資料結構裡
```clike=
static void update_statistics(int64_t *exec_times, uint8_t *classes)
{
for (size_t i = 0; i < number_measurements; i++) {
int64_t difference = exec_times[i];
/* Cpu cycle counter overflowed or dropped measurement */
if (difference <= 0) {
continue;
}
/* do a t-test on the execution time */
t_push(t, difference, classes[i]);
}
}
```
#### 證明兩條線不同
* ttest.h 的 struct 宣告，分別由 mean[i] 代表 Sample mean ， m2[i] 代表 Sample standard deviation ， 和 n[i] Sample size ， 而三個變數均為長度為 2 的陣列，儲存兩種 classes 的資料
```clike=
typedef struct {
double mean[2];
double m2[2];
double n[2];
} t_ctx;
```
* t 的運算在 ttest.c 末段 t_compute ，回傳值 t_value 就是上方計算結果 t
```clike=
double t_compute(t_ctx *ctx)
{
double var[2] = {0.0, 0.0};
var[0] = ctx->m2[0] / (ctx->n[0] - 1);
var[1] = ctx->m2[1] / (ctx->n[1] - 1);
double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;
return t_value;
}
```
* 運算結果 t 會在 report.c 中經由 fabs(t_compute(t)) 運算儲存到 max_t ， 並在副程式下方 if else 的判斷為 < t_threshold_moderate 時才會回傳 true 到 doit 副程式，否則回傳 false ，而 doit 的回傳值就是這個 boolean 值
```clike=
static bool report(void)
{
double max_t = fabs(t_compute(t));
double number_traces_max_t = t->n[0] + t->n[1];
double max_tau = max_t / sqrt(number_traces_max_t);
...
...
if (max_t > t_threshold_bananas) {
return false;
} else if (max_t > t_threshold_moderate) {
return false;
} else { /* max_t < t_threshold_moderate */
return true;
}
}
```
* 在 fixture.c 上方的宣告區可以看到 t_threshold_moderate 的設定值為 10，就是這裡 dudect 的 Welch's t-test 決定是否為 constant time 的基準
```clike=
/* threshold values for Welch's t-test */
#define t_threshold_bananas
500 /* Test failed with overwhelming probability \
*/
#define t_threshold_moderate 10 /* Test failed */
```
## 參考資料
* [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
* [[SOLVED] Compilation Fails for Debian 10](https://forum.freecadweb.org/viewtopic.php?t=37036)
* [dudect: dude, is my code constant time?](https://github.com/oreparaz/dudect)
* [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
* [學生t檢驗](https://zh.wikipedia.org/wiki/%E5%AD%B8%E7%94%9Ft%E6%AA%A2%E9%A9%97#%E7%8D%A8%E7%AB%8B%E9%9B%99%E6%A8%A3%E6%9C%ACt%E6%AA%A2%E9%A9%97)
* [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution#Student's_t-process)
* [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test)
Sign in with Wallet
Connect another wallet