2019q1 Homework1 (lab0)

contributed by < 0xff07 >

開發環境

$ uname -a
Linux OxB16BOOB5 4.18.0-15-generic #16-Ubuntu SMP Thu Feb 7 10:56:39 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:               70
Model name:          Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz
Stepping:            1
CPU MHz:             850.328
CPU max MHz:         3700.0000
CPU min MHz:         800.0000
BogoMIPS:            4988.84
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
L4 cache:            131072K
NUMA node0 CPU(s):   0-7

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.10
DISTRIB_CODENAME=cosmic
DISTRIB_DESCRIPTION="Ubuntu 18.10"

實作

queue_t

因為要求尾端插入與長度查詢的複雜度是

$O(1)$ ，因此在資料結構中加入 tail 與 size 分別紀錄尾端與長度:

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

q_free

void q_free(queue_t *q) 
{
    if (!q)
        return;
    list_ele_t *tmp = q->head;
    while (q->head) {
        tmp = q->head;
        q->head = q->head->next;
        if (tmp->value)
            free(tmp->value);
        if (tmp)
            free(tmp);
    }   
    if (q) 
        free(q);
}

if (q) free(q) 這樣的 if 敘述是多餘，直接寫 free(q) 即可，詳見 free(3)

jserv

若 head 為空，則顯然記憶體已經釋放。若 head 非空，則「釋放 head」可遞迴地視為「釋放串列第一個元素(迴圈中暫存於 tmp) ，並釋放剩下所有元素形成的串列(q -> head -> next)」 。

而再釋放串列中的元素之後，再釋放 q 即可。

若在 free 中傳入空指標，在測試程式中將出現 Attempt to free NULL 的錯誤訊息，並且扣分(儘管 man 中寫到傳入空指標是合法的)。因此這邊所有的 free 都事先檢測是否為空指標。

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh = NULL;
    char *_s = NULL;
    do {
        if (!q)
            break;
        newh = malloc(sizeof(list_ele_t));
        if (!newh)
            break;
        _s = malloc(strlen(s) + 1);
        if (!_s)
            break;
        strcpy(_s, s);
        newh->value = _s;
        newh->next = q->head;
        q->head = newh;
        if (!q->tail)
            q->tail = newh;
        q->size++;
        return true;
    } while (0);
    if (newh)
        free(newh);
    if (_s)
        free(_s);
    return false;
}

使用 do{...} while(0) 配合 break ，達到 goto 的效果，並進行各種例外處理。並在插入後，將屁股尾端維護好。正在思考例外處理與判斷的邏輯是否能夠更精減（立刻回去翻上週作業嗚嗚）。

另外發現若將 14. 15 行改成 cpumpound-literal 的寫法：

*new = (list_ele_t){.value=_s,.next=q->head};

在 git commit 時似乎會被檢查出 memory leak，跑出：

[queue.c:90]: (error) Memory leak: _s
Fail to pass static analysis.

但該作法可以順利通過 qtest 。因此不是很確定這種用法是否將造成 memory leak，或是有什麼潛在的不良影響。相關資料待查。

目前的靜態分析工具是 cppcheck，可能會遇到 false alarm，可搭配 AddressSanitizer (ASAN) 確認是否有 leaks

jserv

q_insert_tail

bool q_insert_tail(queue_t *q, char *s) 
{
    list_ele_t *newh = NULL;
    char *_s = NULL;
    do {
        if (!q)
            break;
        newh = malloc(sizeof(list_ele_t));
        if (!newh)
            break;
        _s = malloc(strlen(s) + 1); 
        if (!_s)
            break;
        strcpy(_s, s); 
        newh->value = _s; 
        newh->next = NULL;
        if (q->head)
            q->tail->next = newh;
        else
            q->head = newh;
        q->tail = newh;
        q->size++;
        return true;
    } while (0);
    if (newh)
        free(newh);
    if (_s)
        free(_s);
    return false;
}

大致上與前一個函數相同，紀錄尾端並在插入後維護好 tail 與 head 的指標。「新增 list_ele_t 」似乎可以寫成一個函式，但發現使用 strdup 時，即使 man 中提到：

The strdup() function returns a pointer to a new string which is a duplicate of the strings. Memory for the new string is obtained with malloc(3), and can be freed with free(3).

即 strdup 中的記憶體由 malloc 配置，但使用 strdup 時測試程式，仍會判定沒有正確配置記憶體（見「其他」），因此尚未測試。

q_remove_head

依照要求，除了釋放記憶體，必要時得將節點中存的字串進行複製。因此照題目要求寫出來：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    list_ele_t *tmp = NULL;
    tmp = q->head;
    q->head = q->head->next;
    if (sp && tmp->value) {
        strncpy(sp, tmp->value, bufsize);
        sp[bufsize - 1] = 0;
    }
    q->size--;
    if (tmp->value)
        free(tmp->value);
    if (tmp)
        free(tmp);
    return true;
}

q_size

直接回傳存好的值大小：

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

q_reverse

假定

$L=[1,\dots ,k-1,k\dots ,n]$ ，則：

1. 若串列為空，或是串列僅有一個元素。則自己就是自己的反轉

2. 若已經有前

   $k$ 個元素反轉的串列
   $L^{\prime }=[k-1\dots 0]$:
   $$[k-1\dots 0]\cup [k,k+1\dots n]$$

   則將第

   $k$ 個元素加入反轉串列的頭部：
   $$[k,k-1\dots 0]\cup [k+1\dots n]$$

   就能構造出前

   $k+1$ 個元素反轉的串列。以此遞推下去。

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;
    if (q->head == q->tail)
        return;
    list_ele_t *buf[3] = {q->head, q->head->next, q->head->next->next};
    q->head->next = NULL;
    q->tail = q->head;
    while (buf[2]) {
        buf[1]->next = buf[0];
        buf[0] = buf[1];
        buf[1] = buf[2];
        buf[2] = buf[2]->next;
    }
    buf[1]->next = buf[0];
    q->head = buf[1];
}

前 2 個 if 敘述描述的是第 1. 中的狀況; 而其後的程式用於處理 2. 中的狀況。

我覺得這樣的實作看起來並不一目瞭然。似乎有待改進。

---

測試程式討論

記憶體管理

在 harness.[ch] 當中，可以看到記憶體管理相關的內容。該記憶體管理機制相關說明如下：

1. 將原先的 malloc 與 free 使用 test_malloc 與 test_free 取代。該部份可見 harness.h 最後面：

   ​​​​/* Tested program use our versions of malloc and free */
   ​​​​#define malloc test_malloc
   ​​​​#define free test_free
   

   所以實際上，在 queue.c 中呼叫 malloc 與 free 時，其實式分別呼叫 test_malloc 與 test_free 兩個函式。以下都用 test_malloc 與 test_free 稱呼該二函式（而不是 malloc 與 free）。

2. 所有因呼叫 test_malloc 得來的記憶體，實際上是紀錄在一個名為 allocated 的一個 doubly-linked list 中。該 linked list 結點的結構為 block_ele_t，定義在 harness.c 中：

   ​​​​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;
   

   在這個結構體中，最後一個成員 payload[0] 是實際給呼叫者使用的記憶體開頭。該成員使用到的 GCC 中 Array of Length Zero 特徵。該功能簡便處在於：若結構體中的最後一個成員是大小為 0 的陣列，那麼可以透過 malloc(sizeof(block_ele_t) + 希望 payload 後面接著多少記憶體) 來達成「最後一個成員大小可以任意指定」的效果（另外一個好處是 malloc 跟 free 一次就可以完成，不用替 payload 開頭的記憶體再 malloc 一次）。malloc_test 中可以發現以下程式：

   ​​​​void *test_malloc(size_t size)
   ​​​​{
   ​​​​    if (noallocate_mode) {
   ​​​​        report_event(MSG_FATAL, "Calls to malloc disallowed");
   ​​​​        return NULL;
   ​​​​    }
   ​​​​    if (fail_allocation()) {
   ​​​​        report_event(MSG_WARN, "Malloc returning NULL");
   ​​​​        return NULL;
   ​​​​    }
   ​​​​    block_ele_t *new_block =
   ​​​​        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
   ​​​​    ...
   

   這個技巧表現在程式的 malloc(size + sizeof(block_ele_t) + sizeof(size_t)) 當中。但除了 sizeof(block_ele_t) 與 size 之外， 還多了一個 sizeof(size_t) 的大小。這是因為使用者實際可使用的記憶體，前後被兩個 size_t 整數包著，裡面各自紀錄著兩個 Magic Number，作為驗證這塊記憶體是否是由 test_malloc 分配的依據，以及作為記憶體是否有產生越界等不佳使用的依據。

   查閱 C99/C11 規範中，是否有類似 gcc "Arrays of Length Zero" 的標準規範，又，Variable-length arrays (VLA) 為何在 Linux 核心不被允許呢？
   

   jserv

3. 位於記憶體之前的 magic number，實際上就是結構體中 magic_header 這個成員，其值會在 test_malloc 中被指定為 MAGICHEADER，也就是 0xdeadbeef ; 在記憶體尾端的 size_t 整數，數值必定為 MAGICFOOTER，也就是 0xbeefdead。

4. 因為要回傳給使用者的指標實際上是 payload 的位置，因在程式中另外有 find_footer 跟 find_header 這兩個函式作為輔助。前這傳入 block_ele_t* ，回傳位於 payload 尾端 magic number 的位址。如 test_malloc 中有一段指定尾端 magic number 的程式：

   ​​​​*find_footer(new_block) = MAGICFOOTER;
   

   而後者則是傳入使用者呼叫後得到的記憶體開頭，反推該記憶體所屬的 block_ele_t 的開頭位置。這兩個函式除了用在 test_malloc 當中，也會用再 test_free 當中。在呼叫 test_free 時，使用者傳入的，實際上是 payload 的位置，但釋放記憶體時，除了該記憶體之外，該記憶體所屬的結構體，也要一併釋放。因此需要有一個尋找該記憶體所屬開頭的方法。

   該二函數的原理不難理解。給定 block_ele_t，尾端的 magic number，由 payload_size 進行推算即可; 對於反推記憶體所屬的結構體，則是利用 sizeof(block_ele_t) 反推，並且尋找反推過後的記憶體是否在 allocated 的清單中。若沒有，則推論為錯誤的配置。

   而在 find_header 中有檢測傳入指標是否為空的設定。

   我懷疑這是一個不能使用 calloc 跟 strdup 的理由。但目前還沒確認該二函數中的 malloc 是否有被影響到。

5. test_free 中用的原理類似：首先用 find_header 找出使用者準備釋放的記憶體，其所屬的結構體有沒有再 allocated 裡面。若傳入的指標為空指標，或是該記憶體不屬於任何一個節點，find_header 內部會分別傳出「試圖釋放空指標」或「記憶體損壞」等警告。

6. 若順利找到該記憶體所屬的節點，接著檢驗尾端的 magic number 是否仍為 MAGICFOOTER，作為記憶體有沒有被越界存取等狀況的判斷依據。若比對結果發現不合，也會發出該區段記憶體損壞的警告。

7. 若確認結果無誤，則將記憶體區段前後的 magic number 都設成 MAGICFREE。並且將記憶體內容都用 FHILLCHAR 填充。最後移出 allocated 這個 doubly-linked list。

   不確定為什麼要先把 magic number 都改掉之後再釋放。我猜測是同樣大小的記憶體如果又被 malloc ，但裡面仍有 magic number 時，會造成誤判，以為不合法的記憶體其實是合法的。

   提示: 思考 malloc() 得到的記憶體空間是否會跟輸入的空間一樣大？若不是，是否意味著我們要額外處理？
   

   jserv

8. 在分配記憶體時，每呼叫一次 test_malloc ，allocate_count 就會 +1; 而每呼叫一次 test_free ，該數值就會 -1。因此程式即將結束時，判斷該數值，即可知道是否有妥當地釋放記憶體。

shell 實作

輸入一個指令時，會經過下面這些 function call 一路到 parse_arg 。這個函數會解譯使用者的輸入：

[#0] 0x555555557c93 → parse_args(line=0x55555555e6a0 <linebuf> "it LookAtMe\n", argcp=0x7fffffffda88)
[#1] 0x555555557f21 → interpret_cmd(cmdline=0x55555555e6a0 <linebuf> "it LookAtMe\n")
[#2] 0x555555558dd8 → cmd_select(nfds=0x1, readfds=0x7fffffffdaf0, writefds=0x0, exceptfds=0x0, timeout=0x0)
[#3] 0x555555558f42 → run_console(infile_name=0x0)
[#4] 0x5555555569c2 → main(argc=0x1, argv=0x7fffffffded8)

之後，interpret_cmda 會在 cmd_list 這個 struct CELE 為元素的 singly linked list 中找對應的指令。cmd_list 會在 main 裡面的 cmd_init 跟 console_init 呼叫時初始化。

找到之後，struct CELE 這個結構體中有個 operation成員，儲存每個指令的結構體中的 operation 是個包住待測試的函數的 wrapper：

typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
}

程式執行到這邊之後，會將剛剛 parse 到的輸入傳給他。以下面這個指令為例：

cmd> ih LookAtMe

parse_arg 完後，執行相應的測試程式時，call stack 如下:

[#0] 0x5555555596bc → q_insert_tail(q=0x555555563b50, s=0x555555563cc0 "LookAtMe")
[#1] 0x555555555ae6 → do_insert_tail(argc=0x2, argv=0x555555563d60)
[#2] 0x555555557e93 → interpret_cmda(argc=0x2, argv=0x555555563d60)
[#3] 0x555555557f36 → interpret_cmd(cmdline=0x55555555e6a0 <linebuf> "it LookAtMe\n")
[#4] 0x555555558dd8 → cmd_select(nfds=0x1, readfds=0x7fffffffdaf0, writefds=0x0, exceptfds=0x0, timeout=0x0)
[#5] 0x555555558f42 → run_console(infile_name=0x0)
[#6] 0x5555555569c2 → main(argc=0x1, argv=0x7fffffffded8)

新增命令

有了上面的資訊後，可以知道設計好 do_* 函數，並在 console_init 中呼叫 add_cmd("<instruction>", <do_*>, "<documentation>")，就可以增加新指令。比如說在 console.c 中增加：

bool do_hello(int argc, char *argv[])
{
    return printf("Hello, World\n") ? 1 : 0;
}

並在 console_init 中多增加：

static void console_init()
{
    add_cmd("new", do_new, "                | Create new queue");
    add_cmd("free", do_free, "                | Delete queue");
    ...
    add_cmd("hello", do_hello, "                | print Hello, World.");
    ...
}

可參照 你所不知道的 C 語言：前置處理器應用篇 提及的 # (Stringification/Stringizing; 字串化) 和 ## (concatenation; 連結; 接續) 使用技巧，簡化上述程式碼

jserv

重新編譯之後，在 qtest 的命令列中輸入 hello，就可以發現指令成功新增：

$ ./qtest 
cmd>hello
cmd>hello
Hello, World

若使用 help，則會發現對應的說明新增進去了：

cmd>help
Commands:
	#	 ...            | Display comment
	free	                | Delete queue
	hello	                | print Hello, World.
	help	                | Show documentation
 	ih	 str [n]        | Insert string str at head o

select_cmda 裡面還有用 select() ，man select 對應的說明為：

select() and pselect() allow a program to monitor multiple file descriptors, waiting until one or more of the file descriptors become "ready" for some class of I/O operation (e.g., input possible). A file descriptor is considered ready if it is possible to perform a corresponding I/O operation (e.g., read(2) without blocking, or a sufficiently small write(2)).

但是忘記他要怎麼用，正在查。

qtest.c

int main(int argc, char *argv[])
{
    /* To hold input file name */
    char buf[BUFSIZE];
    char *infile_name = NULL;
    char lbuf[BUFSIZE];
    char *logfile_name = NULL;
    int level = 4;
    int c;

    while ((c = getopt(argc, argv, "hv:f:l:")) != -1) {
        switch (c) {
        case 'h':
            usage(argv[0]);
            break;
        /* ...                  */
        /* skip other cases     */
        default:
            printf("Unknown option '%c'\n", c);
            usage(argv[0]);
            break;
        }
    }
    queue_init();
    init_cmd();
    console_init();
    set_verblevel(level);
    if (level > 1) {
        set_echo(true);
    }
    if (logfile_name)
        set_logfile(logfile_name);
    add_quit_helper(queue_quit);
    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;
}

最前面的 getopt 的迴圈用來解譯啟動 qtest 時有的 commandline arguement，並做出相應動作。接著進行 3 個初始化動作。首先是 queue_init:

static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

這邊的測試是用一個全域變數 q 作為測試的 linked-list。除了把錯誤次數的計數 fail_count 設成 0 之外，還註冊了 2 個訊號的 signa handler，其中 SIGSEV （segmentattion fault 會發出的訊號）的處理常式是：

void sigsegvhandler(int sig)
{
    trigger_exception(
        "Segmentation fault occurred.  You dereferenced a NULL or invalid "
        "pointer");
}

而另外一個 SIGALARM 的處理函式是：

void sigalrmhandler(int sig)
{
    trigger_exception(
        "Time limit exceeded.  Either you are in an infinite loop, or your "
        "code is too inefficient");
}

可以發現兩者均使用了 trigger_exception 。而 trigger_exception 的定義，則是：

void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

除了設定相關的變數，全域變數 error_message 指給錯誤訊息之外，還有一個 siglongjump。而這個 siglongjmp 會跳到哪裡去呢？觀察一下那邊有 sigsetjmp。會發現在 exception_setup 裡面：

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;
    }
}

可以發現：除了暫停 SIGALARM 的計時之外，還會進行 report_event，猜測這是用來回報錯誤訊息。把他打開看看：

void report(int level, char *fmt, ...)
{
    va_list ap;
    if (!verbfile)
        init_files(stdout, stdout);
    if (level <= verblevel) {
        va_start(ap, fmt);
        vfprintf(verbfile, fmt, ap);
        fprintf(verbfile, "\n");
        fflush(verbfile);
        va_end(ap);
        if (logfile) {
            va_start(ap, fmt);
            vfprintf(logfile, fmt, ap);
            fprintf(logfile, "\n");
            fflush(logfile);
            va_end(ap);
        }
    }
}

會發現這是一個接受不定量參數數目的函數，主要的功能是輸出錯誤訊息。

接著翻了 The Linux Programming Interface，發現了一些使用訊號的細節：

1. sigsetjmp 跟 siglongjmp 是能在 signal handler 內部使用的非區域跳躍。不使用 setjmp, longjmp 的理由是：

   The sa_mask field allows us to specify a set of signals that aren’t permitted to interrupt execution of this handler. In addition, the signal that caused the handler to be invoked is automatically added to the process signal mask. This means that a signal handler won’t recursively interrupt itself if a second instance of the same signal arrives while the handler is executing.

   以及：

   However, there is a problem with using the standard longjmp() function to exit from a signal handler. We noted earlier that, upon entry to the signal handler, the kernel automatically adds the invoking signal, as well as any signals specified in the act.sa_mask field, to the process signal mask, and then removes these signals from the mask when the handler does a normal return.

   What happens to the signal mask if we exit the signal handler using longjmp()? The answer depends on the genealogy of the particular UNIX implementation.

   即：當某個 signal handler 被觸發時，該訊號會在執行 signal handler 時會被遮罩住，並在 signal handler 回傳時恢復; 而在裡面使用 longjmp 時，解除訊號遮照的行為有可能不會發生(是否解除則依照實作決定)。為了保證在非區域跳躍後能夠恢復，所以規範了另一個能在 signal handler 中呼叫的 sigsetjmp 跟 siglongjmp。

2. jmp_ready 的技巧：

   Because a signal can be generated at any time, it may actually occur before the target of the goto has been set up by sigsetjmp() (or setjmp()). To prevent this possibility (which would cause the handler to perform a nonlocal goto using an uninitialized env buffer), we employ a guard variable, canJump, to indicate whether the env buffer has been initialized. If canJump is false, then instead of doing a nonlocal goto, the handler simply returns.

   因為訊號有可能在任何時候發生，包含 sigsetjmp 正在處理而未處理完 sigjmp_buf 的時候。如果這時候 signal handler 又進行 siglongjmp，那麼將產生錯誤。改良方法是設立一個 jmp_ready 變數，表示「sigjmp_buf 是否準備好」，並且在可能進行 siglongjmp 的 signal handler 中先檢查這個變數，以確保 sigjmp_buf 有正確地初始化。

init_cmd

看這個名字大概可以猜到是用來吃初始化測試用的 command line 的。裡面是：

void init_cmd()
{
    cmd_list = NULL;
    param_list = NULL;
    err_cnt = 0;
    quit_flag = false;
    add_cmd("help", do_help_cmd, "                | Show documentation");
    add_cmd("option", do_option_cmd,
            " [name val]     | Display or set options");
    add_cmd("quit", do_quit_cmd, "                | Exit program");
    add_cmd("source", do_source_cmd,
            " file           | Read commands from source file");
    add_cmd("log", do_log_cmd, " file           | Copy output to file");
    add_cmd("time", do_time_cmd, " cmd arg ...    | Time command execution");
    add_cmd("#", do_comment_cmd, " ...            | Display comment");
    add_param("verbose", &verblevel, "Verbosity level", NULL);
    add_param("error", &err_limit, "Number of errors until exit", NULL);
    add_param("echo", &echo, "Do/don't echo commands", NULL);
#if 0
    add_param("megabytes", &mblimit, "Maximum megabytes allowed", NULL);
    add_param("seconds", &timelimit, "Maximum seconds allowed",
              change_timeout);
#endif
    init_in();
    init_time(&last_time);
    first_time = last_time;
}

前面是在初始化一堆全域變數，這些變數代表的功能暫時不知道。但後面的 add_cmd 可以猜測是加入新的指令。進去看看實作：

void add_cmd(char *name, cmd_function operation, char *documentation)
{
    cmd_ptr next_cmd = cmd_list;
    cmd_ptr *last_loc = &cmd_list;
    while (next_cmd && strcmp(name, next_cmd->name) > 0) {
        last_loc = &next_cmd->next;
        next_cmd = next_cmd->next;
    }
    cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
    ele->name = name;
    ele->operation = operation;
    ele->documentation = documentation;
    ele->next = next_cmd;
    *last_loc = ele;
}

看到這邊，再參照 console.h 中的結構體：

typedef bool (*cmd_function)(int argc, char *argv[]);

/* Information about each command */
/* Organized as linked list in alphabetical order */
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

可以發現：所有的 command line 指令是用一個 singlely-linked list 儲存的，而每個結構是用一個名稱(name) ，一個指向對應功能的函數的 function pointer, 以及一個字串的說明(documentation)構成。而插入的手法類似 insertion sort，將所有命令由字典序排好。

而另外一方面，add_param 也是用類似的運作方式：

/* Add a new parameter */
void add_param(char *name,
               int *valp,
               char *documentation,
               setter_function setter)
{
    param_ptr next_param = param_list;
    param_ptr *last_loc = &param_list;
    while (next_param && strcmp(name, next_param->name) > 0) {
        last_loc = &next_param->next;
        next_param = next_param->next;
    }
    param_ptr ele = (param_ptr) malloc_or_fail(sizeof(param_ele), "add_param");
    ele->name = name;
    ele->valp = valp;
    ele->documentation = documentation;
    ele->setter = setter;
    ele->next = next_param;
    *last_loc = ele;
}

而對應的結構體為 param_ele 跟 param_ptr：

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;
};

例外處理

在 interpret_cmda 中，如果有找到指令，會呼叫對應的 struct CELE 中的 operation 成員。operation 每個函數的型別都是 bool (*do_something) (int, char**)，對應的命名就是 do_<operation name> 的那些函數。在呼叫 operation 時，是用如下的方法：

static bool interpret_cmda(int argc, char *argv[])
{
    ...
    if (next_cmd) {
        ok = next_cmd->operation(argc, argv);
        if (!ok)
            record_error();
        } else {
            report(1, "Unknown command '%s'", argv[0]);
            record_error();
            ok = false;
        }
    }
    return ok;
}            

檢測 segmantation fault 或時間超過

如果收到 SIGSEGV 或是 SIGALRM，那麼就會跳進 signal handler 裡面; 而 signal handler 會執行 siglongjmp。會跳到那邊呢? 可以注意到: 每個 do_<operation_name> 型式的函數，都會有如下面這段程式：

    if (exception_setup(true)) {
        for (r = 0; ok && r < reps; r++) {
            bool rval = q_insert_tail(q, inserts);
            if (rval) {
                qcnt++;
                if (!q->head->value) {
                    report(1, "ERROR: Failed to save copy of string in list");
                    ok = false;
                }
            } else {
                fail_count++;
                if (fail_count < fail_limit)
                    report(2, "Insertion of %s failed", inserts);
                else {
                    report(1,
                           "ERROR: Insertion of %s failed (%d failures total)",
                           inserts, fail_count);
                    ok = false;
                }

            ok = ok && !error_check();
        }
    }
    exception_cancel();

假定測試程式沒寫錯，那唯一會發出 SIGSEGV

當執行流程第一次(或說「不是因為 signal handler 跳來這邊」)時，會呼叫 exception_setup。看裡面的內容：

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;
    }
}

這邊我覺得有點怪：如果 longjmp 到一個已經回傳的函數裡面，不是未定義行為嗎？或是 siglongjmp 這方面有什麼不一樣的細節？

設計新的實驗並搭配 GDB 去驗證

jserv

可以知道：第一次呼叫他時，exception_setup 的功能是設立一個 sigjmp_buf，並回傳 true;

回到原來的 if(exception_setup(true)) 中，如果是第一次回傳，那麼那麼 if，會開始測試函數。如果測試函式的過程中，發生任何錯誤（也就是發出 SIGSEGV 或 SIGALRM 訊號），就會立刻跳回 signal handler。signal handler 會印出錯誤訊息，並進行 siglongjmp。由 exception_setup 的程式可以知道又是跳到 exception_setup(true) 裡面(這裡我認為理解有誤。因為就我的理解，如果 longjmp 到已經回傳的函式中，是未定義行為)。但這時會回傳 false，因此跳過測試函數的過程，直接結束測試並回傳 ok 值。

檢測錯誤的結果

如果在執行作業要求的函數中，沒有發出任何訊號，就接著檢測回傳結果是否正確。這方面來說相對簡單：就是一堆 if 分狀況討論，如果不對，就印出對應的錯誤。