# 2019q1 Homework2 (lab0)
contributed by < `ArielWu0203` >
###### tags: `linux_2019`
* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [作業要求](https://hackmd.io/@sysprog/HyFQpqgPB)
* [github](https://github.com/ArielWu0203/lab0-c)
## Overview
* a queue is a pointer of type `queue_t *`.
* Two special cases:
* ==a NULL queue== is one for which the pointer has value NULL.
```cpp=
queue_t *q = NULL;
```
* ==An empty queue== is one pointing to a valid structure, but the head field has value NULL.
```cpp=
queue_t *q = malloc(queue_t);// address is valid
q->head = NULL;
```
## Programming Task
`q new` : Create a new, empty queue.
`q free` : Free all storage used by a queue.
`q insert head` : Attempt to insert a new element at the head of the queue (LIFO discipline).
`q insert tail` : Attempt to insert a new element at the tail of the queue (FIFO discipline).
`q remove head` : Attempt to remove the element at the head of the queue.
`q size` : Compute the number of elements in the queue.
`q reverse`: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.
==意思是改變 pointer 就好，不能 free 或是 allocate elements 。==
## 實作
* ==queue.h==:
為了 `q_insert_tail` and `q_size` require O(1),
所以加入了 `*tail` and `size` field.
```cpp=
/* Queue structure */
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
* ==q new== :
`void * malloc(int n);`
n 為要求的 bytes 數。malloc成功時，則返回 address，malloc 失敗時，則返回 NULL。
malloc 後分配得到的空間是未初始化的。所以在要使用空間時，需用 memset 來初始化為 0。
`void * memset (void * p,int c,int n) ;`
p 為 address，c 為需要初始化的值(這裡我設定為 0)，n 為需要被初始化的 bytes 數。
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL) // q is a NULL ponter.
return NULL;
memset(q, 0, sizeof(queue_t));
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
* ==q free==:
```cpp
void q_free(queue_t *q)
{
if (q == NULL)
return;
list_ele_t **indirect = &(q->head);
list_ele_t *prev = (*indirect);
while ((*indirect) != NULL) {
if ((*indirect)->value != NULL)
free((*indirect)->value);
(*indirect) = (*indirect)->next;
free(prev);
q->size--;
prev = (*indirect);
}
q->tail = NULL;
free(q);
}
```
* ==q insert head==:
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (q == NULL)
return false;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
memset(newh, 0, sizeof(list_ele_t));
/* +1 is the end of string (00) */
newh->value = malloc(sizeof(char) * strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
strncpy(newh->value, s, strlen(s));
if (q->size == 0)
q->tail = newh;
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
* ==q insert tail==:
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
if (q == NULL)
return false;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
memset(newh, 0, sizeof(list_ele_t));
/* +1 is the end of string (00) */
newh->value = malloc(sizeof(char) * strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
memset(newh->value, 0, sizeof(char) * strlen(s) + 1);
strncpy(newh->value, s, strlen(s));
if (q->size == 0) {
q->head = newh;
q->tail = newh;
newh->next = NULL;
q->size++;
return true;
}
q->tail->next = newh;
q->tail = newh;
newh->next = NULL;
q->size++;
return true;
}
```
* ==q remove head== :
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->size == 0)
return false;
list_ele_t **indirect = &(q->head);
if (sp != NULL) {
memset(sp, '\0', bufsize);
strncpy(sp, (*indirect)->value, bufsize - 1);
}
list_ele_t *prev = (*indirect);
if ((*indirect)->value != NULL)
free((*indirect)->value);
(*indirect) = (*indirect)->next;
free(prev);
--(q->size);
if (q->size == 0)
q->tail = NULL;
return true;
}
```
* ==q size== :
```cpp=
int q_size(queue_t *q)
{
/* in O(1) time */
if (q == NULL)
return 0;
return q->size;
}
```
* ==q reverse==:
```cpp=
void q_reverse(queue_t *q)
{
if (q == NULL || q->size == 0 || q->size == 1)
return;
q->tail = q->head;
list_ele_t **indirect = &(q->head);
list_ele_t *prev = (*indirect);
list_ele_t *curr = (*indirect)->next;
while (curr != NULL) {
(*indirect) = curr->next;
curr->next = prev;
prev = curr;
curr = (*indirect);
}
(*indirect) = prev;
q->tail->next = NULL;
return;
}
```
### Result
```cpp=
$ make test
...
---TOTAL 100/100
```
## 自動評分系統運作的原理
在 `Makefile` 中:
```cpp=
test: qtest scripts/driver.py
scripts/driver.py
```
所以我去找了 `scripts/driver.py`:
在 **135 行**中 :
```cpp=
optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])
```
`getopt` 是用來處理命令行參數，
`'hp:t:v:A'` 表示為 `-h -p (參數) -t (參數) -v (參數) -A`
`'valgrind'` 表示為 `--valgrind`
在 **usage(name) function** 中:
是用來輸出參數的使用方法。
```cpp=
$ ./scripts/driver.py -h
Usage: ./scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]
-h Print this message
-p PROG Program to test
-t TID Trace ID to test
-v VLEVEL Set verbosity level (0-3)
```
`verbosity level` 表示輸出的詳細程度。
`-A` : 最後會輸出每個 trace file 的分數 (以 JASON string 形式)
可以用不同的參數來測試，預設為
`-p (./qtest)`
`-t (trace directory 中的所有檔案)`
`-v 0`
`-valgrind (false)`
`-A (false)`
* console.{c,h} : Implements command-line interpreter for qtest
* report.{c,h} : Implements printing of information at different levels of verbosity
## harness.[ch]
在 `README` 中有提到 :
`harness.{c,h}` : Customized version of malloc and free to provide rigorous testing framework (藉由改版過後的 malloc 和 free 來**嚴格**維護記憶體的使用)
改版過後的 malloc 和 free 是什麼? 去看了 `harness.h` 後發現:
```cpp=
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
```
所以在 `qtest.c` 裡使用的 malloc 和 free 都是 call test_malloc & test_free function。
* `test_malloc` function 中:
```cpp=
void *test_malloc(size_t size)
{
...
/* 除了原本就要配置的空間大小，
* 再加上 block 來 maintain 空間的使用，
* 也在最後加了 sizeof(size_t) 當作 magic footer 的空間。
*/
block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));
...
new_block->magic_header = MAGICHEADER;
/* 原本的空間大小 */
new_block->payload_size = size;
/* 找到 magic_footer 應該要放入的起始 address ，並把值填入。 */
*find_footer(new_block) = MAGICFOOTER;
/* allocate 原本就要的空間大小
* FILLCAHR 為 magic number，作為初始化用。
*/
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
return p;
}
```
* `*find_footer` function 中:
```cpp=
static size_t *find_footer(block_ele_t *b)
{
/* 找到 magic_footer 的 address 並回傳 */
size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
return p;
}
```
* `test_free` function 中:
```cpp=
void test_free(void *p)
{
...
/* 找到 block 的開頭和結尾 */
block_ele_t *b = find_header(p);
size_t footer = *find_footer(b);
/* 偵錯 */
if (footer != MAGICFOOTER) {
report_event(MSG_ERROR,
"Corruption detected in block with address %p when "
"attempting to free it",
p);
error_occurred = true;
}
/* 將 block field value 換成 free */
b->magic_header = MAGICFREE;
*find_footer(b) = MAGICFREE;
memset(p, FILLCHAR, b->payload_size);
/* Unlink from list */
block_ele_t *bn = b->next;
block_ele_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
free(b);
allocated_count--;
}
```
### 巨集的使用
從上面的 code 中，可以發現 `MAGICHEADER` `MAGICFREE` `MAGICFOOTER` 用來檢測在 malloc 和 free 時有沒有出錯，還有 `FILLCAHR` 作為初始化用。 (這些皆為 magic number )
>題外話 : 認真看了一下 `#define MAGICHEADER 0xdeadbeef` 這行，覺得這取名也太特別了，就去 google 了一下，意外查到有趣的小知識，有興趣可以點 [link](https://www.techbang.com/posts/4153-deadbeef-media-player) & [magic number--wiki](https://en.wikipedia.org/wiki/Magic_number_(programming))
## qtest 的行為和裡頭的技巧
### signal
* [Reference:SIGNAL(2)](http://man7.org/linux/man-pages/man2/signal.2.html)
```cpp=
typedef void (*sighandler_t)(int);
// dclare signaler_t as pointer to function(int) returning void.
sighandler_t signal(int signum, sighandler_t handler);
```
當接收到不同的 `signum` 參數，會有 handler 來處理。
`SIGSEGV` : Invalid memory reference.(想要取一個 NULL 或是不存在的 pointer)
`SIGALRM` : Timer signal from ALARM(2).
```cpp=
unsigned int alarm(unsigned int seconds);
```
在 `harness.c` 中:
```cpp=
/*
* Prepare for a risky operation using setjmp.
* Function returns true for initial return, false for error return
*/
bool exception_setup(bool limit_time)
{
if (sigsetjmp(env, 1)) {
...
if (limit_time) {
alarm(time_limit); // 這裡 time_limit 為 1 (static int time_limit = 1;)
time_limited = true;
}
return true;
}
}
```
## Valgrind
>Valgrind is a GPL'd system for debugging and profiling Linux programs. With Valgrind's tool suite, you can automatically detect many memory management and threading bugs.
>[reference](http://www.valgrind.org/info/about.html)
### 運作原理
* Valid-value (V) bits : 會記住哪些 variable 是否有值。
* Valid-address (A) bits : 會記住哪些空間被分配出去。
* Reference:
[Details of Memcheck's checking machinery](http://www.valgrind.org/docs/manual/mc-manual.html#mc-manual.machine)
### 本程式的使用
* [Guide to valgrind](https://web.stanford.edu/class/archive/cs/cs107/cs107.1166/guide_valgrind.html)
#### 參數
`--quiet` : 只打印錯誤
`--leak-check=full --show-leak-kinds=all` : check for leak.
#### memory lost
* definitely lost:
heap-allocated memory that was never freed to which the program no longer has a pointer. Valgrind knows that you once had the pointer, but have since lost track of it. This memory is definitely orphaned.
* indirectly lost:
heap-allocated memory that was never freed to which the only pointers to it also are lost. For example, if you orphan a linked list, the first node would be definitely lost, the subsequent nodes would be indirectly lost.
* possibly lost:
heap-allocated memory that was never freed to which valgrind cannot be sure whether there is a pointer or not.
* still reachable: heap-allocated memory that was never freed to which the program still has a pointer at exit (typically this means a global variable points to it).
::: info
使用問題 : 若我執行下列程式，會有 `ERROR: Time limit exceeded.` 和 `ERROR: Freed queue, but 1 blocks are still allocated` 訊息。
```
$ valgrind ./qtest
cmd>new
cmd>new
q = []
cmd>ih dolphin 1000000
cmd>ih dolphin 1000000
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
Insertion of dolphin failed
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>quit
cmd>quit
Freeing queue
ERROR: Freed queue, but 1 blocks are still allocated
==4389== 48 bytes in 1 blocks are definitely lost in loss record 1 of 2
==4389== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4389== by 0x404CF5: test_malloc (harness.c:130)
==4389== by 0x405251: q_insert_head (queue.c:86)
==4389== by 0x4014F9: do_insert_head (qtest.c:166)
==4389== by 0x403A9C: interpret_cmda (console.c:218)
==4389== by 0x403B3D: interpret_cmd (console.c:239)
==4389== by 0x4049AA: cmd_select (console.c:605)
==4389== by 0x404B0E: run_console (console.c:642)
==4389== by 0x40263A: main (qtest.c:583)
==4389==
==4389== 56 bytes in 1 blocks are still reachable in loss record 2 of 2
==4389== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4389== by 0x404CF5: test_malloc (harness.c:130)
==4389== by 0x405203: q_insert_head (queue.c:77)
==4389== by 0x4014F9: do_insert_head (qtest.c:166)
==4389== by 0x403A9C: interpret_cmda (console.c:218)
==4389== by 0x403B3D: interpret_cmd (console.c:239)
==4389== by 0x4049AA: cmd_select (console.c:605)
==4389== by 0x404B0E: run_console (console.c:642)
==4389== by 0x40263A: main (qtest.c:583)
==4389==
```
:::
是超過了可執行時間，所以我去找了 `sigalrmhandler` (處理 SIGALRM signal 的 handler function )，發現 call `trigger_exception` function :
```cpp=
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
* `int sigsetjmp(sigjmp_buf env, int savesigs);` :
[link](https://linux.die.net/man/3/sigsetjmp)
save stack context for nonlocal goto (意思是會存目前的stack)
return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context.
* `env` : 存 stack
* `savesigs` : 不為 0 時，也會把 signals 存起來。
* `void siglongjmp(sigjmp_buf env, int val);`
:
[link](https://linux.die.net/man/3/siglongjmp)
siglongjmp() also restores the signal mask that was saved by sigsetjmp(3)
了解了 `siglongjmp` 和 `siglongjmp` 後，在 `harness.c` 中找到了 `siglongjmp` :
```cpp=
bool exception_setup(bool limit_time)
{
if (sigsetjmp(env, 1)) {
/* Got here from longjmp */
jmp_ready = false;
if (time_limited) {
alarm(0);
time_limited = false;
}
if (error_message) {
report_event(MSG_ERROR, error_message);
}
error_message = "";
return false;
} else {
/* Got here from initial call */
jmp_ready = true;
if (limit_time) {
alarm(time_limit);
time_limited = true;
}
return true;
}
}
```
會 jump 到最近一次的 `exception_setup`，因為藉由 valgrind 發現出錯的地方在 `do_insert_head (qtest.c:166)` :
```cpp=
bool do_insert_head(int argc, char *argv[])
{
...
if (exception_setup(true)) {
for (r = 0; ok && r < reps; r++) {
bool rval = q_insert_head(q, inserts);
...
}
}
exception_cancel();
show_queue(3);
return ok;
}
```
重新回到上次儲存的 stack，這次 `exception_setup(true)` 回傳 false ，不再 malloc 了，但是上一次`exception_setup(true)` 回傳的是 true，所以 malloc a block，因為是 dynamic allocate，所以 stack 還原了，但是 block 卻沒有 free !
## dudect 工具
* Statistcal analysis (not static anaylysis)
* ==Leakage detection techniques== take two sets of measurements for two different input data classes.
* 常用的 leakage deteciotion : ==fix-vs-random tests==
the first class input data is fixed to a constant value, and the second class input data is chosen at random for each measurement.
* t-test : [Welch’s t-test](http://highscope.ch.ntu.edu.tw/wordpress/?p=73780)
Sign in with Wallet
Connect another wallet