# 2019q1 Homework1 (lab0)
###### tags: `sysprog2019` `dev_record`
contributed by < `HTYISABUG` >

## Environment

$ uname -a
Linux GL552VW 4.15.0-45-generic #48-Ubuntu SMP Tue Jan 29 16:28:13 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ 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:               94
Model name:          Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
Stepping:            3
CPU MHz:             3091.593
CPU max MHz:         3500.0000
CPU min MHz:         800.0000
BogoMIPS:            5184.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7

## Implementation
### queue_t
為了滿足 `q_insert_tail` & `q_size` 時間複雜度 $O(1)$ 的要求
在 structure 內補上 tail & size 以取得 queue 的尾端與長度

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    size_t size;
} queue_t;

### q_new
依據註解補上 allocation error 的判斷式
以及 member 的初始化

### q_free
先確認 queue 不為 `NULL`
再以迴圈將各個 element 釋放
最後才釋放 queue

void q_free(queue_t *q)
{
    if (!q) {
        return;
    }

    list_ele_t *indic = q->head;
    while (indic) {
        q->head = indic->next;
        free(indic->value);
        free(indic);
        indic = q->head;
    }
    free(q);
}

### q_insert_head
依序判斷 queue 不為 `NULL` 、malloc 成功與否
如果字串複製失敗，就將 element 釋放並回傳錯誤
最後更新 queue 的內容

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    // if (!q || !(newh = malloc(sizeof(list_ele_t)))) {
    if ((!q) || !(newh = malloc(sizeof(list_ele_t)))) {
        return false;
    }

    if (!(newh->value = strdup(s))) {
        free(newh);
        return false;
    }

    if (!q->tail) {
        q->tail = newh;
    }

    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

第四行的寫法在 commit 時會報錯 memory leak
檢查後發現是括號導致的執行順序錯誤
OR operator 兩側都以括號包裝即可解決

### q_insert_tail
以 tail 直接取得尾端
其餘操作與 `q_insert_tail` 相同

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    // if (!q || !(newt = malloc(sizeof(list_ele_t)))) {
    if ((!q) || !(newt = malloc(sizeof(list_ele_t)))) {
        return false;
    }

    if (!(newt->value = strdup(s))) {
        free(newt);
        return false;
    }

    newt->next = NULL;
    q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

第四行的問題同 `q_insert_head`
以括號包裝可以解決

### q_remove_head
補上 queue 不為 `NULL` 或空的判斷
更新 queue 的 member data
新增字串複製以及記憶體釋放的部份

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head) {
        return false;
    }

    list_ele_t *head = q->head;
    q->head = q->head->next;
    q->size--;

    if (sp) {
        strncpy(sp, head->value, bufsize - 1);
        sp[bufsize-1] = '\0';
    }

    free(head->value);
    free(head);
    return true;
}

### q_size
以 queue 的 member `q_size` 直接取得長度
以達成時間複雜度 $O(1)$ 的要求

### q_reverse
同樣補上 queue 不為 `NULL` 或空的判斷
用兩個新指標來儲存新的 head & tail
再循序將 elements 重新指向

void q_reverse(queue_t *q)
{
    if (!q || !q->head) {
        return;
    }

    list_ele_t *newh = NULL, *newt = q->head;
    list_ele_t *indic = q->head;
    while (indic) {
        indic = indic->next;
        q->head->next = newh;
        newh = q->head;
        q->head = indic;
    }

    q->head = newh;
    q->tail = newt;
}

實作方法示意圖如下

## Auto Judge Program
使用 `cscope` 幫助追蹤程式流程

### Procedure Analysis
- `queue_init`
- 初始化 queue
- 設定 signal handler
- `init_cmd`
- 初始化 shell 指令
- `console_init`
- 增加 queue API 到 shell 指令
- `run_console`
- shell 開始實際執行

### Detail
#### Signal Handler
皆為 `trigger_exception` 的 wrapper
`trigger_exception` 使用 `siglongjmp` 返回至 main loop
返回點則是在設定 shell 指令時使用 `sigsetjmp`
紀錄當下的 stack pointer 、 instruction pointer 等資訊

之所以不使用 `setjmp` 、 `longjmp` 是因為這裡牽涉到 signal 遮罩
如果使用以上兩個 function 會導致 signal handler 失效

從這幾個 function 的行為來看
我猜想它們在 kernel 內的定位是用在 context switch 的部份

#### Commands & Parameters
設定中以 singly linked list 儲存新增的項目

#### Quit Helper
為一方便增加程式結束時的處理的方法
用這方法能避免增加處理時需要修改多個檔案的問題

#### Waiting for input
相比一般等待使用者輸入會用 `scanf` 等來自 standard I/O 的 function
`qtest` 中使用了 `select` 作為替代方案

`select` 的用途是監視 file descriptor 是否可用
包含 input, output, except 皆可**同時**監視

雖然在 `qtest` 中只用於監視單一 input 來源
但這種監視多個 file descriptor 的功能
我猜想或許在任務排程時會有作用

### Memory Leak When Input File Not Exist
在了解程式運作流程的時候
因為打錯檔名而意外發現檔案不存在時會產生 memory leak

Trace 程式碼發現是這種情況下會因為 `run_console` 回傳 false
而使 `ok` 變為 false
進而導致下一行的 `finish_cmd` 不被執行

修改 `finish_cmd` 與 `ok` 的順序來修復這個問題

:::warning
嘗試提交 pull request
:notes: jserv
:::

// qtest.c
int main(int argc, char *argv[])
{
    ...
    bool ok = true;
    ok = ok && run_console(infile_name);
    // ok = ok && finish_cmd();
    ok = finish_cmd() && ok;
    return ok ? 0 : 1;
}

### Invalid Data Type
以下節錄自 `ISOIEC 9899:201x` 6.7.6.2 節 陣列宣告

> If the expression is a constant expression,
> it shall have a value greater than zero.

而 `harness.c` 中這個 struct 違反這段的規定
不知道是不是我搞錯什麼了

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    /* Marker to see if block seems legitimate */
    size_t magic_header;
    /* Invalid ? */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

追加：
看來這個寫法來自 [GCC extension](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html)
作為動態指定 struct member 大小的方法使用
這樣同時還能確保記憶體的連續

對應 C99 的 flexible array member
操作方法基本相同，需要預留足夠的記憶體
但如果沒有預留任何記憶體給 flexible array member
這樣會導致 undefined behavior

> If this array would have no elements,
> it behaves as if it had one element but the behavior is undefined
> if any attempt is made to access that element
> or to generate a pointer one past it.