# 2019q1 Homework1 (lab0)
contributed by < `zodf0055980` >
###### tags: `Linux 核心設計`
## 開發環境
```shell
$ uname -a
Linux yuan-X555LF 4.15.0-45-generic
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
```
## 實作Queue要求
主要是去實作 FIFO & LIFO queue，需滿足以下功能:
- q_new 去建立一個新的 Queue
- q_free 把整個 Queue 所佔的記憶體給釋放掉
- q_insert_head 在 head 插入 element
- q_insert_tail 在 tail 插入 element
- q_remove_head 從 head 移除一 element
- q_size 回傳目前 Queue 的大小
- q_reverse 把 Queue 反轉
:::success
2/26 簡化程式碼
:::
### queue_t
```clike
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
為了實現 q_insert_tail 和 q_size 的時間複雜度為 $O(1)$ ，所以加入指向 Queue 尾端的 pointer 以及儲存 size 大小。
## q_new
```clike
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return 0;
q->size = 0;
q->head = NULL;
q->tail = NULL;
return q;
}
```
這邊需要注意 malloc() 如果請求失敗，會回傳 NULL ，因此需要注意 malloc() 請求失敗的狀況。
## q_insert_head
```clike
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;
int len = strlen(s) + 1;
char *val = malloc(len * sizeof(char));
if (!val) {
free(newh);
return false;
}
memset(val, 0, len);
strncpy(val, s, len - 1);
newh->next = q->head;
newh->value = val;
if (!q->head) {
q->tail = newh;
q->head = newh;
} else {
newh->next = q->head;
q->head = newh;
}
q->size++;
return true;
}
```
這邊需注意 list_ele_t malloc() 成功，但 value malloc() 失敗，需要把 list_ele_t 給 free()，避免多餘的資料占用記憶體。
這邊也注意到自己的不足，居然把 sizeof(s) 當作整個 string 的長度，因為 s 是指標，所以得到的會是指標的大小，而非字串的長度。想起上課講到的，這是愚蠢的程式碼。
此段時間複雜度為 $O(1)$
## q_insert_tail
```clike
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
// int len = sizeof(s) + 1; // '/0' so +1
int len = strlen(s) + 1;
char *val = malloc(len * sizeof(char));
if (!val) {
free(newh);
return false;
}
memset(val, 0, len);
strncpy(val, s, len - 1);
newh->value = val;
newh->next = NULL;
if (!q->head) {
q->tail = newh;
q->head = newh;
} else {
q->tail->next = newh;
q->tail = newh;
}
q->size++;
return true;
}
```
q_insert_tail 和 q_insert_head 相似，時間複雜度為 $O(1)$。
## q_remove_head
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *nexte = q->head;
if (sp) {
memset(sp, '\0', bufsize);
strncpy(sp, nexte->value, bufsize - 1);
}
q->head = q->head->next;
free(nexte->value);
free(nexte);
q->size--;
return true;
}
```
這邊需要注意 sp 需要判斷是否為 NULL，時間複雜度為 $O(1)$。
## q_free
```clike
void q_free(queue_t *q)
{
if (q) {
list_ele_t *p = q->head;
while (p) {
list_ele_t *temp;
temp = p;
p = p->next;
free(temp->value);
free(temp);
}
free(q);
}
}
```
這邊需要注意要先 free value，再free list_ele_t，時間複雜度為 $O(n)$。
## q_size
```clike
int q_size(queue_t *q)
{
if (q)
return q->size;
return 0;
}
```
這邊一開始沒有考慮 q 為 NULL 的狀況，時間複雜度為 $O(1)$。
## q_reverse
```clike
void q_reverse(queue_t *q)
{
if (!q || !q->head || !q->head->next)
return;
list_ele_t *a = NULL;
list_ele_t *b = q->head;
list_ele_t *temp = q->head;
while (b) {
list_ele_t *c;
c = a;
a = b;
b = b->next;
a->next = c;
}
q->head = a;
q->tail = temp;
}
```
這裡特地把以前資料結構的書給拿出來看，利用3個 pointer 去實現 Queue 的反轉。
這邊一開始測試檔一直過不了。
```clike
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
參考學長的共筆紀錄
```clike
$ grep -rn 'Test of truncated strings'
traces/trace-06-string.cmd:1:# Test of truncated strings
```
並至 trace-06-string.cmd 中依序測試一遍，發現如果 Queue 未建立，會出現 Null Dereferencing。因此需判斷 Queue 中是否有多於兩個 element，而此 reverse 時間複雜度為 $O(n)$。
# 自動評分系統運作的原理
在 harness.h 中有這段
```clike
#define malloc test_malloc
#define free test_free
```
他把 malloc 和 free 都對應到 harness.c 中的程式碼，去做相關的檢查，這也是為什麼 segment fault 不會結束程式的原因。
## struct BELE
```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;
```
第一次看到宣告矩陣大小為0的，一查發現原來是 [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html)。透過去 malloc(sizeof(block_ele_t) + 額外的記憶體空間) 便可以利用 unsigned char payload[] 去對額外空間作存取。因此去利用 block_ele_t 去儲存有關分配記憶體的各項資料，去判斷是否有不正當得使用。
:::danger
列出第一手資料，規格書或者編譯器使用手冊
:notes: jserv
:::
:::success
以更正
:::
## test_malloc
```clike
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
```
利用 Arrays of Length Zero 的技巧把 new_block 指派我們想要 malloc() 的大小。並儲存分派記憶體大小和把 magic_header 設為 0xdeadbeef。以及利用 find_footer 去把 block_ele_t 最尾端指向 0xbeefdead。最後利用 double linked list 把分配的記憶體給串聯起來，並回傳實際可用空間的記憶體位址。
如果 test_malloc 成功執行，記憶體的內容會如下圖所示:
這樣便可以透過 magic_header 和 MAGICFOOTER 去判斷對記憶體的操作是否正確。而 magic_header 和 MAGICFOOTER 可為任意的值，主要是拿來判斷正確性。
## test_free
因為 test_malloc 所回傳的值是實際可用空間的記憶體位址，因此需要透過 find_header 找 block_ele_t 所在的記憶體位址。
```clike
block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t));
```
並把 magic_header 和 MAGICFOOTER 指向 0xffffffff 來代表該記憶體區塊已經釋放，並用 FILLCHAR 去填滿。且從 double linked list 移除。
```clike
memset(p, FILLCHAR, b->payload_size);
```
## single的操作
在 qtest 中的 queue_init() 中，透過
```clike
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
```
透過設置信號和 function，只要有 SIGSEGV 和 SIGALRM 的信號，便會執行 sigsegvhandler 和 sigalrmhandler 的 function。
而 SIGSEGV 負責處理的是 Invalid memory reference，一般我們程式如果發生 segmentation fault，便會產生 exception 通知 OS，由 OS 做處理。這也是為甚麼我們平常只要有 segmentation fault 程式就會中斷。而透過 signal() 去設定發生 segmentation fault 的處理 function，這也就是為什麼程式出錯而不會結束的原因。
而 SIGALRM 負責處理的是 Alarm clock。透過 alarm(time_limit) 去設定 timer 幾秒後產生 SIGALRM 的信號，alarm(0) 去取消停止當前的 timer 處理。
在 qtest.c 中對 Queue 的操作都有類似下面的 code:
```clike
if (exception_setup(true))
q = q_new();
exception_cancel();
```
如果一段時間內(此程式為1秒)沒有執行 exception_cancel 去取消 timer 的處理，timer 會產生 Alarm clock 的信號，以確保程式不會有無窮迴圈的情況。
# Reference
[ktvexe 開發紀錄(lab0)](https://hackmd.io/s/HJJtkhYBE)
Sign in with Wallet
Connect another wallet