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 的順序來修復這個問題

嘗試提交 pull request
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
作為動態指定 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.