# 2020q3 Homework1 (lab0)
contributed by < `jonec76` >
###### tags: `sysprog-2020`
> [作業說明](https://hackmd.io/@sysprog/2020-lab0)
## 開發環境
```shell
$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux
```
## 作業要求
實作基本功能，測驗分數達到 100 分，但是加入 `make SANITIZE=1` 之後只有 95 分 ( trace-17 仍錯)，以下是實作過程。
::::info
Jserv 老師上課說：q_reverse 還可以考慮如果 size=2 時，還需要做下面的 while-loop 嗎？
::::
### `q_insert_head(queue_t *q, char *s)`
- **錯誤過程**
- **複製字串出現亂碼**
```shell
cmd> ih jkl
q = [jkl��� qwer���]
```
原因出於 `strncpy(newh->value, s, strlen(s))`，在 [strncpy man page](https://linux.die.net/man/3/strncpy) 提到，以上程式碼會複製 src 的前 n bytes ，但這 n 個 bytes 不包含 null terminator，所以到了 dst 時該字串沒有 null terminator，就在字串的最後面產生亂碼。
解決方法就是改成 `strncpy(newh->value, s, strlen(s)+1)` ，讓 `strncpy` 複製前 n 個 bytes，並且他會在 n+1 的位置放入 '\0'，也就是 null terminator。
- **code**
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
size_t len = strlen(s);
/* TODO: What should you do if the q is NULL? */
if (newh == NULL) {
free(newh);
return false;
}
char *value = malloc((len + 1) * sizeof(char));
if (value == NULL) {
free(newh);
free(value);
return false;
}
newh->value = value;
strncpy(newh->value, s, len + 1);
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
q->size++;
if (q->size == 1) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
return true;
}
```
### `q_free(queue_t *q)`
- **錯誤過程**
```+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
ERROR: Freed queue, but 4 blocks are still allocated
--- trace-04-ops 0/6
```
尚未實作 `q_free()` 之前，執行 `make test` 後會發現 `trace-04-ops` 給了以上的錯誤回應，經過觀察 `trace-04-ops` 知道它使得 list size 達到 6，但是只做了 4 次的 "rh" 刪除，意思就是說在 04-ops 測試結束時，`q->head` 仍然有 2 個 `list_ele_t` 並沒有被刪除。
於是開始查找，這個 `qtest` 是如何得知還剩下多少 block？如何在程式結束（主動按下 ctrl+c）時執行的？
在 `main()` 裏頭有個 function `add_quit_helper(queue_quit)` ，會在一開始將 `queue_quit` 加入 `quit_helpers` queue，`queue_quit` 就是當程式離開之前要執行的 function。當程式執行 `quit` 或者 ==ctrl+c（還不懂為什麼 ctrl+c 會進入 do_quit_cmd）== 時，就會去執行`do_quit_cmd`，裡頭會執行 `quit_helpers` 就會執行到 `queue_quit`。
在 `queue_quit` 裡面會執行 `q_free()` ，並且執行 `allocation_check` ，這個 function 會回傳曾經 allocated 多少個 block 。在 `malloc` 時會對變數 `allocated_count`+1 ，`free` 會 `allocated_count`-1，於是只要當 `allocated_count` 不為 0 時，那就表示還有 block 是沒有被 freed 的。
- **code**
```cpp=
void q_free(queue_t *q)
{
if (!q)
return;
if (q->head == NULL) {
free(q);
return;
}
do {
list_ele_t *tmp = q->head;
char *tmp_value = tmp->value;
q->head = q->head->next;
free(tmp_value);
free(tmp);
} while (q->head != NULL);
free(q);
}
```
### `q_sort()`
::::info
Jserv 老師上課說：我們應該思考，當 list 的 size 應該大於多少時，才做 q_sort？因為做 linked-list 的 sort 成本過大
::::
- **錯誤過程**
- **Disallowed malloc**
最一開始的想法是把 q->head 這條 list 的所有 value 複製到一個新的陣列，並且使用 c library 提供的 `qsort()` 來完成，但是在 `make test` 時遇到 “Disallowed malloc” 錯誤。
在 `qtest.c` 裏頭的 `do_sort` 看到了以下的程式碼
```cpp
set_noallocate_mode(true);
if (exception_setup(true))
q_sort(q);
exception_cancel();
set_noallocate_mode(false);
```
於是再去看 `set_noallocate_mode(true);` 裏頭的程式碼，可以看到他是將 `noallocate_mode` 設為 `true`，再去找 `noallocate_mode` 用在哪裡，可以發現跟 `void *test_malloc` 有關。
得到的結論是，當 `qtest` 在執行時，因為在 `harness` 可以找到 `#define malloc test_malloc`，也就是自行額外定義 `malloc()` ，當在程式裡面執行 `malloc()` 時，其實都是執行 `void *test_malloc()` ，而該 function 在分配一塊所需空間並且回傳 pointer 之前，會先做一連串的檢查，因為在 `do_sort()` 裡面有將 `noallocate_mode` 設定為 `true`，所以會進到 *test_malloc() 的
```cpp
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to malloc disallowed");
return NULL;
}
```
也就可以在該作業規定 "在 sort 時不能額外分配新的空間，只能用 `q->head` list 內部做 swap"。
- **Time limit exceeded**
- 在跑 qsort 時無法通過 `trace-15-perf` 、 `trace-16-perf` 的測驗，原因是因為實作的 `ih` 不夠有效率的儲存資料
- **`trace-16-perf`**
原本是透過 `insertion sort` 來實作 q->head 的排序，但是在這個測試 ih 大量的 data，於是想說用 q1 上課的 [測驗題](https://hackmd.io/@sysprog/linux2020-quiz1) 提到的 optimizing merge-sort 去 sort，即通過此測驗。
```c=1
list_ele_t *left, *right, *tail, *half;
left = right = tail = half = start;
while(tail){
if(tail->next!=NULL )
tail = tail->next;
if(tail->next!=NULL )
tail = tail->next;
else break;
half = half->next;
}
right = half->next;
half->next = NULL;
left = sort(left);
right = sort(right);
```
原本的 merge-sort 會產生出 T(n) = T(n-1)+n 的時間複雜度，也就是 `O(n^2)`，於是在這邊將該程式改成 T(n) = 2T(n/2)+n 的方法，讓 merge-sort 的 left 以及 right 都是目前 size 的一半，並且去跑遞迴。
- **code**
```cpp=1
void q_sort(queue_t *q)
{
if (!q)
return;
q->head = mergeSortList(q->head);
}
list_ele_t *mergeSortList(list_ele_t *start)
{
if (!start || !start->next)
return start;
list_ele_t *left, *right, *tail, *half;
left = tail = half = start;
while (tail) {
if (tail->next != NULL)
tail = tail->next;
if (tail->next != NULL)
tail = tail->next;
else
break;
half = half->next;
}
right = half->next;
half->next = NULL;
left = mergeSortList(left);
right = mergeSortList(right);
for (list_ele_t *merge = NULL; left || right;) {
if (!right || (left && strcasecmp(left->value, right->value) <= 0)) {
if (!merge) {
start = merge = left;
} else {
merge->next = left;
merge = merge->next;
}
left = left->next;
} else {
if (!merge) {
start = merge = right;
} else {
merge->next = right;
merge = merge->next;
}
right = right->next;
}
}
return start;
}
```
### `q_remove_head(queue_t *q, char *sp, size_t bufsize)`
- **錯誤過程**
- **`ERROR: Freed queue, but 3 blocks are still allocated`**
當 free 了 `list_ele_t *tmp` 之後，卻沒有 free `tmp->value` 此 char pointer 指到的空間。
- **`ERROR: copying of string in remove_head overflowed destination buffer.`**
```cpp
if (i != string_length + STRINGPAD) {
report(1,
"ERROR: copying of string in remove_head overflowed "
"destination buffer.");
ok = false;
}
發現在執行 `trace-06-strings` 會有以上錯誤，去看了之後發現是在這邊出錯，`i=31` 但是 `string_length + STRINGPAD=30+1024`，這和 `trace-06-strings` 裡頭的 `option length 30` 有關係。
options length=30，意思是最大呈現出字串的長度為 30，在該行設定完 length=30 的下一行，是 `rh meerkat_panda_squirrel_vulture` ，這行進來的 `argv[1]` 參數是 30 個字，而試著用 `gdb` 去找錯誤，發現在 `removes[31]` 的位置並不是 'X'，而是 "w"，也就是 pop 出來的字 "meerkat_panda_squirrel_vulture_wolf" 的第 31 個位置 w，於是修改成以下程式碼
```cpp
strncpy(sp, tmp->value, bufsize);
sp[bufsize-1] = '\0';
```
使得複製最大只到 bufsize(含 null terminator) 的大小位置，因為這段複製的 src 有可能不包含 '\0'，所以根據 `strncpy` 並不會在 dst 的最後一個位置加入 '\0'，這部分需要自行處理。
- **Program received signal SIGSEGV, Segmentation fault.**
在 `trace-09-robust` 偵測出以下程式碼產生問題
```c=1
sp[bufsize - 1] = '\0';
```
於是去看了 `trace-09-robust` 裡頭的 op，發現 `rhq` 的設計，是希望單純移除 head 而不要複製，這邊會在 `do_remove_head_quiet` 的 function 傳入 bufsize=0 的參數，所以加入 if-condition 去偵測即可。
- **code**
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
if (q == NULL || q->size == 0)
return false;
q->size--;
list_ele_t *tmp = q->head;
if (bufsize != 0) {
strncpy(sp, tmp->value, bufsize);
sp[bufsize - 1] = '\0';
}
q->head = q->head->next;
free(tmp->value);
free(tmp);
return true;
}
```
### `queue_t *q_new()`
- **錯誤過程**
- **Program received signal SIGSEGV, Segmentation fault.**
在 `trace-10-malloc` 偵測出以下程式碼產生問題
```cpp
queue_t *q = malloc(sizeof(queue_t));
q->head = NULL;
```
於是去觀察 "option malloc 50" 裡頭的參數，這項 op 會使得 fail_probability=50（初始值是 0 ），也就是他會有 0.5 的機率會產生 malloc 失敗（在 `test_malloc` 會回傳 `NULL` 給 pointer），加入 NULL check 即可。
- **code**
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
if (!q)
return q;
q->head = NULL;
q->size = 0;
return q;
}
```
### 其他錯誤
- 使用 `make SANITIZER=1` 後再跑 `make test`，會在 trace-17 出現以下的錯誤，評量分數只有 95，仍在找尋解決辦法。
>
==126215==ERROR: AddressSanitizer: global-buffer-overflow on address 0x5647678ad960 at pc 0x56476789d9be bp 0x7fff5b8849d0 sp 0x7fff5b8849c0
- **`git commit` fail to pass static analysis**
偵測到以下程式碼會有 `memory leak` 的問題
```cpp
newh->value = malloc((len + 1) * sizeof(char));
if (newh->value == NULL)
return false;
```
參考了 [simple-rules-to-avoid-memory-leaks-in-c](https://mousomer.wordpress.com/2010/11/03/simple-rules-to-avoid-memory-leaks-in-c/) 裡面提到的，在 malloc 一塊記憶體給一變數後，如果沒有 free() 該空間，則會發生 memory leak 的問題。另外，也有提到在 malloc 的時候，應將記憶體空間 malloc 給一個 char 變數，再透過 assign 的方式讓 pointer(這邊是 `newh->value`) 指到該空間作操作。
於是將程式碼改成
```cpp
char *value = malloc((len + 1) * sizeof(char));
if (value == NULL) {
free(newh);
free(value);
return false;
}
newh->value = value;
```
### `研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;`
- **說明**
在 `trace-17` 檔案裡頭可以看到會使用 simulation mode 去測試函式 `insert_tail` 以及 `q_size`。
以 `is_insert_tail_const` 為例，裡頭可以看到 `doit` 函式做了一連串的運算並把時間記錄下來，程式碼如下
```c=1
prepare_inputs(input_data, classes);
measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
bool ret = report();
```
`prepare_inputs` 裡頭的 `randombytes(input_data, number_measurements * chunk_size);` 能夠使 `input_data` 的每個 element 獲得 0~255 的亂數([ 參考 stack ](https://stackoverflow.com/questions/11147044/dev-urandom-range))，這部分是透過讀取 `fd = open("/dev/urandom", O_RDONLY);` 將亂數後放入 `input_data`，另外，也隨機產生 classes (0~1) 以及 `random_string`。
在 `measure` 時，將會執行 `insert_tail` 若干次，每次插入的資料是 `random_string` * `insert_tail[i]` 筆，並且將執行前後的 cpucycles
記錄下來，並在 `differentiate` 獲得執行時間。
`update_staticstics` 是將執行時間隨機的加入 class0 或者 class1 裡面，並且更新該 class 的平均數、m2(變異數)，最後當計算出 t-value 大於 10 時，則會回報 "ERROR: Probably not constant time"。其原理是使用 Welch t-testing 檢測兩個 class 的分佈相近程度，若該函式執行時間是常數時間的話，則 input 不管大小如何都不會影響其執行時間。
- 如何產生隨機的 `input_data`
```c=1
for (size_t i = 0; i < number_measurements; i++) {
classes[i] = randombit();
if (classes[i] == 0)
*(uint16_t *) (input_data + i * chunk_size) = 0x00;
}
```
`classes[i]` 會隨機的得到 0 或 1 的值，接著若是 0 的話，會將 0x00 放入對應的位置。原先的 `input_data` 是 `uint8_t`，也就是每格大小為 1 byte，但這邊轉型成 `input_data + i * chunk_size` 指向的是一個 2 bytes 的大小位置，依據 little endian 規則，0x00 會從最低位開始放（目前指標指導的位置），接著後面就是補 0。
接著看 `measure` 裡頭的程式碼
```c=1
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * chunk_size) % 10000);
)
```
可以看到這邊取值時，是取出指標目前指到的 2 bytes 的值出來，所以數字範圍才會是從 0 到 65535。
接著，思考同學的 pr [commit:master (#42)](https://github.com/sysprog21/lab0-c/commit/2d975875eecad8ddc0c5fc5ec6d4582f9a706439)，原先的做法是將 chunk 的前面 2 個 bytes 清為 0，新的 pr 的做法是將整個 chunk 都清空，這樣的優點在目前的隨機取值似乎無法體現出來，如下
```c=1
*(uint16_t *) (input_data + i * chunk_size) % 10000);
```
但若是將 `*(uint16_t *)` 改成 `*(uint32_t *)`，也就是希望能夠使亂數的範圍更大（0~$2^{32}$）時，因為每次取出 4 bytes，此時若是舊的方法則會有未清空的部分（因為舊的方法只清空每個 chunk 的起始 2 bytes），是此 pr 的一項改進。
- ~~更改 `update_statistics` 計算方式~~
- ~~這邊其實是有疑問的~~，(==發現自己想法錯誤==)。舊的 code 如下
```c=1
// t_push(t_ctx *ctx, double x, uint8_t class)
double delta = x - ctx->mean[class];
ctx->mean[class] = ctx->mean[class] + delta / ctx->n[class];
ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
```
每次會傳入一個執行時間 x，並且將此 x 去更新對應的 class 的 mean，然而，計算標準差的公式中的平均值，應該是整個 class 的平均值，而不是像此 "動態" 調整過後的平均值。
但是看了同學的筆記 ([oscardshiang](https://hackmd.io/@oscarshiang/sysprog_lab0-c)) 以及 [welfords-method](https://jonisalonen.com/2013/deriving-welfords-method-for-computing-variance/#:~:text=The%20definition%20can%20be%20converted,squared%20differences%20from%20the%20mean.) 才知道這樣計算方式的優點，是能夠減少 overflow 的風險，以及能以 single pass 將 data 遍歷一遍即可得出平均值以及標準差。
算平均值的部分較為直觀，故以下僅摘錄計算標準差的部分，在 `t_push` 裡頭能看到
```c=1
double delta = x - ctx->mean[class];
ctx->m2[class] = ctx->m2[class] + delta * (x - ctx->mean[class]);
```
上述的 code 若做了移項，即可知道 `delta * (x - ctx->mean[class])` 化成數學式如下
$\sum_{k=1}^{N}(x_i - \overline{x}_{N})^2 - \sum_{k=1}^{N-1}(x_i - \overline{x}_{N-1})^2$
也就是程式碼的 $m2_N - m2_{N-1}$，接著經過一連串的化減（可參考 [welfords-method](https://jonisalonen.com/2013/deriving-welfords-method-for-computing-variance/#:~:text=The%20definition%20can%20be%20converted,squared%20differences%20from%20the%20mean.)）才得到下面式子
$(x_n - \overline{m}_{n-1})(x_n - \overline{m}_{n})$
其中 $\overline{m}_{n}$ 表示算到第 n 個值的 mean 平均數，也就是 code 中的 `delta * (x - ctx->mean[class])`
## TODO
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 挑戰題
Sign in with Wallet
Connect another wallet