# 2021q1 Homework1 (lab0)
contributed by < `ccs100203` >
###### tags: `linux2021`
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
Stepping: 9
CPU MHz: 2635.475
CPU max MHz: 3800.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-7
```
---
## 作業要求
> [lab0](https://hackmd.io/@sysprog/2020-lab0)
詳細閱讀 [C Programming Lab ](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式。
- q_new: 創一個空的 queue
- q_free: 釋放掉一個 queue
- q_insert_head: 在 head 插入一個 element (LIFO)
- q_insert_tail: 在 tail 插入一個 element (FIFO), O(1)
- q_remove_head: 把 head 的 element 移除
- q_size: return queue 的大小
- q_reverse: 將 queue 反轉，不配置或釋放任何的 element
- q_sort: 將 queue 由小排到大, sort by nature sort
---
## 開發過程
### q_new
檢查 malloc 是否正常運作
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
// if malloc return NULL
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
### q_free
要記得先清掉 value
```cpp
void q_free(queue_t *q)
{
// NULL queue
if (q == NULL)
return;
for (list_ele_t *tmp = q->head; q->head; tmp = q->head) {
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
### q_insert_head
一開始在檢查 malloc 時沒有 `free(newh)`，導致 `make test` 時有記憶體未釋放，然後沒有做 `memset` 的話，會遇到 char* 裡頭塞了怪怪的東西，所以後來就先把他清空了。
```cpp
bool q_insert_head(queue_t *q, char *s)
{
// NULL queue
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
// if malloc fail
if (newh == NULL)
return false;
newh->value = malloc((strlen(s) + 1) * sizeof(char));
// if malloc fail
if (newh->value == NULL) {
free(newh);
return false;
}
memset(newh->value, 0, (strlen(s) + 1) * sizeof(char));
strncpy(newh->value, s, strlen(s));
newh->next = q->head;
q->head = newh;
q->size++;
if (q->size == 1)
q->tail = newh;
return true;
}
```
### q_insert_tail
跟 insert head 滿像的
```cpp
bool q_insert_tail(queue_t *q, char *s)
{
// NULL queue
if (q == NULL)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
// if malloc fail
if (!newt)
return false;
newt->value = malloc((strlen(s) + 1) * sizeof(char));
// if malloc fail
if (newt->value == NULL) {
free(newt);
return false;
}
memset(newt->value, 0, (strlen(s) + 1) * sizeof(char));
strncpy(newt->value, s, strlen(s));
newt->next = NULL;
// if queue is empty
if (q->size == 0) {
q->head = newt;
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
q->size++;
return true;
}
```
### q_remove_head
照著註解的方式去做，一開始 `q->size` 忘記扣，導致 size 錯誤
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
// NULL or empty queue
if (q == NULL || q->head == NULL)
return false;
if (sp != NULL && q->head->value) {
memset(sp, 0, bufsize);
strncpy(sp, q->head->value, bufsize - 1);
}
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
q->size--;
return true;
}
```
### q_size
確認是否為 NULL queue
```cpp
int q_size(queue_t *q)
{
return (q == NULL) ? 0 : q->size;
}
```
### q_reverse
用了 `prev` `curr` `next` 三個指標去紀錄目前反轉的位置，一路從頭做到尾
```cpp
void q_reverse(queue_t *q)
{
// NULL queue or element < 2
if (q == NULL || q->size < 2)
return;
list_ele_t *prev, *next, *curr;
prev = NULL;
next = q->head->next;
curr = q->head;
while (curr != NULL) {
curr->next = prev;
prev = curr;
curr = next;
if (next != NULL)
next = next->next;
}
curr = q->head;
q->head = q->tail;
q->tail = curr;
}
```
探索是否有其他作法
TODO
### q_sort
參照 [Linkd List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 的 `merge sort` 做更改，起初使用遞迴版本時遇到 stack 爆掉的問題，後來用 iterate 的版本時遇到了不能 `malloc` 的問題，於是又更改了一下寫法才能通過。
在舊版的寫法中，會遇到一開始 `head` 不知道要放什麼，所以需要在 5~13 行去提前判斷 `head` 應該要放什麼，在新版中改為用一個 pointer to pointer `tmp` 去指著 `head`，就可以在做 while 時把 node 直接放進 `tmp` 並同時把第一個 node 給 `head`，隨後只需要把 `tmp` 一直往後接就可以把 list 串起來。
#### 舊版
```cpp=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *temp = NULL, *q = NULL;
// init the nodes
if (strnatcmp(l1->value, l2->value) < 0) {
q = l1;
temp = l1;
l1 = l1->next;
} else {
q = l2;
temp = l2;
l2 = l2->next;
}
// sort and connect two list
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
temp->next = l1;
temp = temp->next;
l1 = l1->next;
} else {
temp->next = l2;
temp = temp->next;
l2 = l2->next;
}
}
// connect remaining node
if (l1)
temp->next = l1;
if (l2)
temp->next = l2;
return q;
}
```
#### 新版
```cpp=36
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *head = NULL;
list_ele_t **tmp = &head;
// sort and connect two list
// don't move head, use tmp traverse all list
while (l1 && l2) {
if (strnatcmp(l1->value, l2->value) < 0) {
*tmp = l1;
l1 = l1->next;
} else {
*tmp = l2;
l2 = l2->next;
}
tmp = &((*tmp)->next);
}
// connect remaining node
if (l1)
*tmp = l1;
if (l2)
*tmp = l2;
return head;
}
```
```cpp
list_ele_t *mergeSortList(list_ele_t *head)
{
// merge sort
if (!head || !head->next)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// split list, find the middle of 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 = mergeSortList(head);
list_ele_t *l2 = mergeSortList(fast);
// merge sorted l1 and sorted l2
return merge(l1, l2);
}
```
一開始忘記 update q->tail 導致錯誤
```cpp
void q_sort(queue_t *q)
{
// NULL queue or element < 2
if (q == NULL || q->size < 2)
return;
q->head = mergeSortList(q->head);
// update q->tail pointer
list_ele_t *tmp = q->head;
while (tmp->next) {
tmp = tmp->next;
}
q->tail = tmp;
}
```
---
## Valgrind
- #### massif 實驗
寫 `q_free` 時，沒注意到 value 的釋放而導致錯誤，這邊試試看沒有釋放 value，明顯看出在最後的差別
```cmd
new
ih RAND 10000
sort
free
quit
```
- 有 free value
- 沒有 free value
---
## Dude, is my code constant time?
- [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)
- Measure execution time
- 分出 fix-vs -random 兩種不同 class
- 利用現代 CPU 的 cycle counters，可精準測量執行時間
- 為了降低環境影響，每次測量的 class 隨機，且會在測量之前將 input 做好
- post-processing
- Cropping: 排除因為 OS 或其他無關因素導致的極端值
- Higher-order preprocessing: 根據不同的 statistical test 做出不同調整
- `dudect` 相關
- `constant.c` 的 `measure`
分為 `test_size` 與 `test_insert_tail` 兩個 mode，測試是不是 O(1)
先在 `insert_head` 放入 `get_random_string` 得到的隨機 string，之後做 test 時會前後 call `cpucycles` 放入 `after_ticks` 跟 `before_ticks` ，之後相減就可以得到 cycle 數量
```c=60
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();
}
}
```
- `fixture.c`: 判斷是否在誤差範圍內
`test_tries` 代表整體測試的次數
在 10000 筆之中，使用 500 與 10 兩個 threshold，如果差距在 5% 以上則代表整個程式完全不符合 constant time
==未搞懂 threshold 如何設置==
```c=
#define enough_measurements 10000
#define test_tries 10
#define t_threshold_bananas 500
#define t_threshold_moderate 10
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;
}
```
:::info
2021/02/24
在 cppcheck 2.3 dev 會遇到 unmatchedSuppression 的問題，
無法解讀 pre-commit.hook 內 suppresses 新增的 nullPointerRedundantCheck，
我將 cppcheck 的版本降為 1.9 後解決此問題。
> 提交 pull request 來改進 Cppcheck 相關操作？
> :notes: jserv
:::
Sign in with Wallet
Connect another wallet