# 2019q1 Homework1 (lab0)
contributed by < `rebvivi`>
###### tags: `linux2019`
* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [F01: lab0](https://hackmd.io/s/BJA8EgFB4#%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
## 作業要求
- FIFO 和 LIFO 實作 queue
我們是用 linked list 來實現
* queue_t：queue 的基本架構
* q_size：計算 queue 中有幾個 element
* q_new：新增一個 empty 的 queue
* q_free：清除整個 queue
* q_insert_head：使用 LIFO 的方法新增 element
* q_remove_head：移除 queue 的第一個 element
* q_insert_tail：使用 FIFO 的方法新增 element
* q_reverse：把 queue 裡面的 element 反轉
- `解釋自動評分系統運作的原理`以及`提及 qtest 的行為和裡頭的技巧`
- 所需要的 C 語言認知 :
* Explicit memory management, as required in C.
* Creating and manipulating pointer-based data structures.
* Working with strings.
* Enhancing the performance of key operations by storing redundant information in data structures.
* Implementing robust code that operates correctly with invalid arguments, including NULL pointers.
:::danger
不要過度簡化作業要求，明明 CMU lab0 要求很多，為何你只看到這句話？工程人員實事求是的精神去哪了？及早脫離「文組^TM^」
:notes: jserv
:::
## 開發環境
```shell
$ uname -a
Linux peiwen-X550VX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
```
## 實作
基本的程式碼架構老師已經都建好了，必須先了解 linked list 以及 queue 的架構才能實作
### queue_t
**queue 的基本架構**
```clike
typedef struct {
list_ele_t *head;
list_ele_t *tail;
size_t size;
} queue_t
```
新增 size 讓 queue 隨時紀錄現在 queue 的大小，
不用從頭到尾跑一遍才能知道 queue 的大小
### q_size
**計算 queue 中有幾個 element**
```clike
int q_size(queue_t *q)
{
if (q == NULL || q->size == 0) {
return 0;
} else {
return q->size;
}
}
```
因為 queue_t 有新增 size 的 index，讓 q_size 的時間複雜度能維持在 $O(1)$
### q_new
**新增一個 empty 的 queue**
```clike
queue_t *q_new()
{
queue_t *q = (queue_t *) malloc(sizeof(queue_t));
if (q != NULL) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
return q;
}
```
要注意 malloc 有沒有配置到記憶體
### q_free
**清除整個 queue**
```clike
void q_free(queue_t *q)
{
if (q != NULL) {
list_ele_t *temp;
while ((q->head) != NULL) {
temp = q->head;
q->head = temp->next;
free(temp->value);
free(temp);
}
}
free(q);
return;
}
```
記得要先把 element 的 value free 掉之後才能 free 掉 element，
最後再釋放 queue 之前配置的記憶體。
### q_insert_head
**使用 LIFO 的方法新增 element**
```clike=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newnode = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newnode == NULL) {
return false;
// free(newnode);
}
if (q->size == 0) {
q->tail = newnode;
}
newnode->value = strdup(s);
newnode->next = q->head;
q->head = newnode;
q->size++;
return true;
}
```
==過程中犯的錯誤==
第 7 行的 if ，如果已經判斷 newnode == NULL ，再 free(newnode) 的話 ，會出現以下的錯誤
```cpp
Attempt to free NULL
```
每次 malloc 都要確認有沒有配置到記憶體，如果配置失敗就要回傳 false 並且 free 剛才 malloc 的東西，避免產生 memory leak 的問題
如果一開始 queue 的 size 是 0 的話，記得要調整 tail
### q_remove_head
**移除 queue 的第一個 element**
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || (q->size) == 0) {
return false;
}
list_ele_t *remove;
remove = q->head;
q->head = q->head->next;
if (sp != NULL) {
memset(sp, '\0', bufsize);
strncpy(sp, remove->value, bufsize - 1);
}
free(remove->value);
free(remove);
q->size--;
return true;
}
```
記得要 free 第一個 element 的 value 再 free 掉 element
### q_insert_tail
**使用 FIFO 的方法新增 element**
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newinsert = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newinsert == NULL) {
return false;
}
newinsert->value = strdup(s);
newinsert->next = NULL;
if (q->size == 0) {
q->head = newinsert;
}
q->tail->next = newinsert;
q->tail = newinsert;
q->size++;
return true;
}
```
每次 malloc 都要確認有沒有配置到記憶體，如果配置失敗就要回傳 false 並且 free 剛才 malloc 的 node，避免產生 memory leak 的問題
如果一開始 queue 的 size 是 0 的話，記得要調整 head
==過程中犯的錯誤==
> 除了 malloc newinsert 之外， newinsert 的 value 也要配置記憶體
```clike
newinsert->value = malloc(strlen(s) + 1);
```
第 12 行使用到 strdup()， 但是會造成 memory allocate 的錯誤
strdup()不是標準的 C 函式，在 [strdup() 的 Linux Man Page](https://www.systutorials.com/docs/linux/man/3-strdup/) 的 Description 中提到：
> The strdup() function returns a pointer to a new string
which is a duplicate of the string s.
Memory for the new string is obtained with malloc(3),
and can be freed with free(3).
我們在 queue.c 所呼叫的 `malloc` 和 `free` 在 qtest 都會改成呼叫 `test_malloc` 和 `test_free`，所以如果我們使用 strdup()，就用不到真正的`malloc` 和 `free`，導致配置記憶體出問題
而 strcpy() 是標準的 C 函式，所以應該改成：
```clike
strcpy(newinsert->value, s);
```
:::danger
「strdup()不是標準的 C 函数，所以在 linux 上使用會有問題」這句陳述的「所以」有問題，GNU/Linux 是符合 POSIX 標準的作業系統，語言標準 (如 C99) 和標準執行環境 (如 POSIX) 之間的關聯，你需要描述。請查證並列出 POSIX.1-2001 規格書描述。在你「舉燭」之前，要讀書。
function 用於數學領域，譯作「函數」，但在程式設計中作為通用 subroutine 的話，譯作「函式」
:notes: jserv
:::
### q_reverse
**把 queue 裡面的 element 反轉**
```clike
void q_reverse(queue_t *q)
{
list_ele_t *current = NULL;
list_ele_t *before = NULL;
list_ele_t *nextnode;
if (q != NULL && q->size > 1) {
current = q->head;
q->tail = current;
while (current != NULL) {
nextnode = current->next;
current->next = before;
before = current;
current = nextnode;
q->head = before;
}
return;
}
}
```
如果 queue 是空的或是 queue 只有一個 element 就不用 reverse
---
## 自動評分系統運作的原理
### harness.[ch]
>在 harness.h 中，我們在 queue.c 所用的 `malloc`和 `free`
都被改成呼叫 `test_malloc` 和 `test_free`
```clike
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free
```
> `block_ele_t` 是一個 `doubly linked list `的結構
```clike
typedef struct BELE {
struct BELE *next;
struct BELE *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_ele_t;
```
> `test_malloc` 實際上需要配置的空間＝
> (我們所要求的 size 大小) + (`block_ele_t` 所需要的空間) + (sizeof(size_t)的空間)，而 sizeof(size_t) 的空間是為了紀錄 `magic_footer`
>`magic_header` 和 `magic_footer`是用來紀錄所配置的記憶體的前後位置，我們將兩者定義為常數
```cpp
/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
```
>如果`magic_header` 和 `magic_footer`的數值被更改了，代表我們寫入的位址超過我們配置記憶體的範圍
>如果是`magic_header`被更動數值，就是寫入的記憶體向`前`超過我們配置的範圍，如果是`magic_footer`被更動數值，就是寫入的記憶體向`後`超過我們配置的範圍
==Q&A==
Q：為什麼當初宣告`block_ele_t`的 structure 的時候不宣告 `magic_footer`？
A：因為我們每次用 `malloc` 所輸入的 size 都不一樣，所以配置空間的結尾
也會不同，`magic_footer` 位置也就不同，所以我們ㄧ要幫`magic_footer`預留一個sizeof(size_t)的空間，之後再用`find_footer`去找到`magic_footer`的位置
:::danger
需要解釋 magic 的用途，最好搭配用另外一個獨立的試驗 (及相關記憶體分析工具) 來說明，避免「舉燭」。
:notes: jserv
:::
> `test_malloc` 所配置的空間紀錄在叫做`allocated`的 `doubly linked list`中，這個 `doubly linked list`中的 `payload[0]`代表我們在 queue.c 用 `malloc`呼叫的記憶體的開頭
>用 `allocate_count`紀錄所配置的記憶體長度，如果沒有歸還完全 `malloc`所配置的記憶體，`allocate_count`的長度就會大於 1 ，並且出現以下的錯誤訊息
```cpp
"ERROR: Freed queue, but %lu blocks are still allocated"
```
```clike
void *test_malloc(size_t size)
{
...
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
...
void *p = (void *) &new_block->payload;
...
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
return p;
}
```
### exeption 處理
exception 的設置目的：
* 如果程式超過 limit_time ，就會發出錯誤訊息
在處理 exception 的時候用到了 [sigsetjmp](https://linux.die.net/man/3/sigsetjmp) ，如果 `sigsetjmp`的值不是 0 ，代表是從 `siglongjmp` 回來的
>setjmp() and sigsetjmp() return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context
而 `siglongjmp` 不 return，在 [siglongjmp的 Linux Man Page](https://linux.die.net/man/3/siglongjmp) 的 Return Value 有提到：
>These functions never return.
==主要概念==
如果 limit_time=true，代表程式是有時間限制的，如果在時間限制內沒有呼叫 `exception_cancel`的話，就會觸發 `trigger_exception` 產生錯誤訊息
>在 qtest 中我們都把 `exception_setup` 中的 limit_time 設成 true
>* 因為並不是從 `setlongjmp` 跳回來的，所以`sigsetjmp`的值是 0
>* 跳到 `exception_setup` 的 17 行執行，此時 jmp_ready = true ， 而 time_limited 最初設定是 false ，現在被改成 time_limited = true
>* 因為 jmp_ready = true 所以執行`trigger_exception`第 6 行的 `siglongjmp`
>* 此時因為是從 `setlongjmp` 跳回來的，`sigsetjmp` 的值變成不是 0 ，所以會執行 `exception_setup`的第 3 行的 if 的內容
>* jmp_ready = false ， time_limited 從 true 被改成 false，report_event 產生錯誤訊息
```clike=
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;
}
}
```
```clike=
void exception_cancel()
{
if (time_limited) {
alarm(0);
time_limited = false;
}
jmp_ready = false;
error_message = "";
}
```
```clike=
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
### console.[ch]
>在 console.h 中，command 和 parameter 都是一個 `linked list` 的結構
>我們利用 `add_cmd`和`add_param`來將 command 和 parameter 加入 `linked list`
```clike
//command
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name;
cmd_function operation;
char *documentation;
cmd_ptr next;
};
```
```clike
//parameter
typedef struct PELE param_ele, *param_ptr;
struct PELE {
char *name;
int *valp;
char *documentation;
/* Function that gets called whenever parameter changes */
setter_function setter;
param_ptr next;
};
```
>在 console.c 中，有一個 `linked list` 的結構用來儲存 input
>
```clike
#define RIO_BUFSIZE 8192
typedef struct RIO_ELE rio_t, *rio_ptr;
struct RIO_ELE {
int fd; /* File descriptor */
int cnt; /* Unread bytes in internal buffer */
char *bufptr; /* Next unread byte in internal buffer */
char buf[RIO_BUFSIZE]; /* Internal buffer */
rio_ptr prev; /* Next element in stack */
};
```
>`parse_args`把所有的 input 都轉換成 (int argc, char *argv[]) 的形式，將所有的 input 都用同一種形式存取，這樣對於呼叫任意 qtest 中的函式也會更加方便
```clike
char **parse_args(char *line, int *argcp)
{
...
*argcp = argc;
return argv;
}
```
### qtest
>在`console_init`裡頭，設定輸入 input 和測試函式的連結
>例如：輸入 input "new"，會執行測試函式"do_new"測試我們在 queue.c 中所打的 q_new
```clike
static void console_init()
{
add_cmd("new", do_new, " | Create new queue");
...
}
```
Sign in with Wallet
Connect another wallet