# 開發紀錄 lab(0) Queue 實作

Contributed by < [`dange0`](https://github.com/dange0) >

###### tags: `sysprog2018`

>兩個 commit message 都沒有具體說明做了哪些修改，請修正
>[name=課程助教][color=red]
>>已修正
>>[name=Dange0]

## 實驗環境

$ cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.5 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.5 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

$ gcc -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)

$ cat /proc/version
Linux version 4.4.0-87-generic (buildd@lcy01-31) (gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4) ) #110-Ubuntu SMP Tue Jul 18 12:55:35 UTC 2017

## Makefile

CC = gcc
CFLAGS = -O0 -g -Wall -Werror

GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest

$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

queue.o: queue.c queue.h harness.h
	$(CC) $(CFLAGS) -c queue.c 

qtest: qtest.c report.c console.c harness.c queue.o
	$(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o

test: qtest scripts/driver.py
	scripts/driver.py

clean:
	rm -f *.o *~ qtest 
	rm -rf *.dSYM
	(cd traces; rm -f *~)

- GIT_HOOKS := .git/hooks/applied
- `:=` 會立即展開的特性，`GIT_HOOKS` 會被馬上賦予值 `.git/hooks/applied`
- $(GIT_HOOKS):
- 因為上面已經被代換為 `.git/hooks/applied`，因此會去檢查 `.git/hooks/applied` 是否存在
- 存在的話，就會直接略過
- 不存在的話，就會去執行 scripts/install-git-hooks

### scripts/install-git-hooks

#!/bin/sh

if ! test -d .git; then
    echo "Execute scripts/install-git-hooks in the top-level directory."
    exit 1
fi

ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit || exit 1
chmod +x .git/hooks/pre-commit

ln -sf ../../scripts/commit-msg.hook .git/hooks/commit-msg || exit 1
chmod +x .git/hooks/commit-msg

touch .git/hooks/applied || exit 1

echo
echo "Git commit hooks are installed successfully."

在 install-git-hook 裡，透過第14行的 `touch` 產生 applied，因此使用者在 make 時，`$(GIT_HOOKS):` 只會被執行一次。

## queue.h

### typedef struct

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail; /* Linked list of elements */
    int size;
    /*
      You will need to add more fields to this structure
      to efficiently implement q_size and q_insert_tail
    */
} queue_t;

為了加速 `q_insert_tail` 與 `q_size` 的速度，在 struct 中額外新增了 `*tail` 與 `size`，在每次的新增或刪減就立即的更新相關數值。

## queue.c
在實做 queue.c 時，主要遇到了 3 跟問題：
1. strdup 無法使用
2. q_remove_head 中修改 *sp 的值出錯
3. q_reverse timeout
### strdup 無法使用
`q_insert_head` 中複製字串不能只是用 strcpy 將字串複製到目標的位置，必須要先分配一塊記憶體空間給他，因此 `strdup` 正是符合這樣的條件，他會先 malloc 一塊空間並放上欲複製的字串，再將其記憶體位置回傳。其看似美好的程式碼如下：

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /* Empty queue handling */
    if (q == NULL)
        return;

    list_ele_t *ptr, *del;
    ptr = q->head;

    /* Free list & value */
    while (ptr != NULL) {
        del = ptr;
        ptr = ptr->next;
        free(del->value);
        free(del);
    }

    /* Free queue structure */
    free(q);
}

bool q_insert_head(queue_t *q, char *s)
{
    /* Empty queue handling */
    if (q == NULL)
        return false;


    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    /* copy string with malloc*/
    newh->value = strdup(s);

    /* update the head ptr */
    newh->next = q->head;
    q->head = newh;

    /* The first */
    if (newh->next == NULL) {
        q->tail = newh;
    }

    /* counter for q_size */
    q->size++;
    return true;
}

測試結果如下：

$ make test
...
---     TOTAL           21/100

$ ./qtest
cmd>new
q = []
cmd>ih a 10
q = [a a a a a a a a a a]
cmd>free
ERROR: Attempted to free unallocated block.  Address = 0x237ccd0
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x237ccd0
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
q = NULL
ERROR: Freed queue, but 11 blocks are still allocated

發現系統在嘗試 `free` 時產生錯誤。初步認為是 `strdup` 出問題，因此決定使用 `strcpy` 與 `malloc` 取代之。

newh->value = malloc(strlen(s) + 1);
if (newh->value == NULL) {
    free(newh);
    return false;
}
strcpy(newh->value, s);

測試結果如下：

$ make test
...
---     TOTAL           100/100

推論成立！不過 `strdup` 到底哪裡錯了呢？在觀看完 [glibc](https://github.com/walac/glibc/blob/master/string/strdup.c) 中的 strdup 實做方式後，發現與自己手刻基本上沒有差異。其 `glibc/strdup.c` 相關程式碼如下：

__strdup (const char *s)
{
  size_t len = strlen (s) + 1;
  void *new = malloc (len);

  if (new == NULL)
    return NULL;

  return (char *) memcpy (new, s, len);
}

經過一番搜索，發現於 `harness.h` 中有定義 `malloc` 與 `free`
**harness.h**

void *test_malloc(size_t size);
void test_free(void *p);

#ifdef INTERNAL

...

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

**harness.c 中的 test_malloc**

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;

/*
  Implementation of application functions
 */
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));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }
    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    void *p = (void *) &new_block->payload;
    memset(p, FILLCHAR, size);
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

這邊明確的展示了 `test_malloc` 的行為，於第 23 行：

block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));

使用者要求 malloc 的空間為 `size` ，然而他會 malloc 一塊更大的空間，包含了 `block_ele_t` 與 `size_t`，並且回傳指標型態為 `block_ele_t`
block_ele_t 是一個 double linked-list 的型態，將 malloc 出去的記憶體做集中的管理
使用者實際要求的空間，會被存在 `block_ele_t` 中的 payload，並於第 23 行將其地址傳給 `*p`

void *p = (void *) &new_block->payload;

最後在 function return 時，將 p 回傳。
因為這樣的實做方式，導致回傳的 p 並非指到 heap 的開始位置，在直接呼叫 free 時就會出錯，必須使用 `test_free` 才能正確的還原 heap 開始的位置，所以不行直接使用 `strdup`。

### q_remove_head 中修改 *sp 的值出錯
在實做 q_remove_head 時，有要求需當 *sp 是 non-NULL 時，需要回傳 buffer size - 1 的值。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* Empty queue handling */
    if (q == NULL)
        return false;

    /*Return false if queue is NULL or empty.*/
    if (q->head == NULL)
        return false;

    /* move the head */
    list_ele_t *del;
    del = q->head;
    q->head = q->head->next;

    /*  If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)*/
    if (sp != NULL) {
        strncpy(sp, del->value, bufsize - 1);
    }
    /* free */
    free(del->value);
    free(del);

    /* counter for q_size */
    q->size--;
    return true;
}

執行結果：

$ make test
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR:  Removed value meerkat_panda_squirrel_vultureXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture
...
---     TOTAL           86/100

判斷為忘記加 null terminator，因此修改第 18 行如下：

if (sp != NULL) {
    memset(sp+bufsize-1, '\0', 1);
    strncpy(sp, del->value, bufsize - 1);
}

執行結果：

$ make test
...
---     TOTAL           100/100

### q_reverse timeout

#### Ver. 1：兩個 for 迴圈
在這個版本中，使用了兩個指標一個指向頭 `ptr_head`，一個指向尾 `ptr_tail`，將這兩個指標所指到的 struct 內部的 value 互換，然而這是一個 single linked-list 的架構，`ptr_tail` 必須透過 `q_size` 與 `ptr_head` 去做推算。這樣的架構就必須要兩個 for 迴圈，一個 for 迴圈是作為 `ptr_head` 走到 q_size/2 的位置，另一個迴圈做的是將 ptr_tail 指到對應的位置。
這樣的執行結果雖然正確，但是數量大的時候，效能會大大降低，因此這邊就開始做架構整體上的修改。
複雜度：O($n^2$)
#### Ver. 2：更改指標方向
為了解決上一個版本複雜度過高的問題，這個版本將會把複雜度降為O(n)，使用的方法為只走訪一次 linked-list，並且將每個 list 的 next 指向前一個 list。為了避免更動 next 值導致 linked-list 斷掉，因此使用了 3 個 pointer： ptr_pre, ptr_now, ptr_next，去做紀錄。
每輪都會將 ptr_now->next 指向 ptr_ptr，並且再將 ptr_pre, ptr_now, ptr_next 依序往下輪替。

void q_reverse(queue_t *q)
{
    /*No effect if q is NULL or empty*/
    if (q == NULL)
        return;
    if (q->size <= 1)
        return;


    list_ele_t *ptr_pre, *ptr_now, *ptr_next;

    /* move to the first windows */
    ptr_pre = q->head;
    ptr_now = ptr_pre->next;
    ptr_next = ptr_now->next;

    /* reverse the pointer next and shift the windows */
    while (ptr_next != NULL) {
        ptr_now->next = ptr_pre;
        ptr_pre = ptr_now;
        ptr_now = ptr_next;
        ptr_next = ptr_next->next;
    }

    /* The last */
    ptr_now->next = ptr_pre;

    /* modify the head and tail */
    q->head->next = NULL;
    q->tail = q->head;
    q->head = ptr_now;
}

實驗結果：

$ make test
...
---     TOTAL           100/100

## 評分機制的解析
在評分系統中，主要需要注意的有兩個部分
1. Exception handling
2. heap 狀態檢查機制

首先可以先了解評分機制的執行流程與檔案間的關係。
從 makefile 中可以看到，在執行`$ make test` 時，`scripts/driver.py` 會被執行，在 `driver.py` 中，他引入了 trace-01-ops, trace-02-ops 等等 script 作為測試之輸入

**driver.py**

class Tracer:
    
    traceDirectory = "./traces"
    qtest = "./qtest"
    verbLevel = 0
    autograde = False

    traceDict = {
        1 : "trace-01-ops",
        2 : "trace-02-ops",
        3 : "trace-03-ops",
        4 : "trace-04-ops",
        5 : "trace-05-ops",
        6 : "trace-06-string",
        7 : "trace-07-robust",
        8 : "trace-08-robust",
        9 : "trace-09-robust",
        10 : "trace-10-malloc",
        11 : "trace-11-malloc",
        12 : "trace-12-malloc",
        13 : "trace-13-perf",
        14 : "trace-14-perf",
        15 : "trace-15-perf"
        }

    traceProbs = {
        1 : "Trace-01",
        2 : "Trace-02",
        3 : "Trace-03",
        4 : "Trace-04",
        5 : "Trace-05",
        6 : "Trace-06",
        7 : "Trace-07",
        8 : "Trace-08",
        9 : "Trace-09",
        10 : "Trace-10",
        11 : "Trace-11",
        12 : "Trace-12",
        13 : "Trace-13",
        14 : "Trace-14",
        15 : "Trace-15"
        }


    maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
...

**trace-01-ops.cmd**

# Test of insert_head and remove_head
option fail 0
option malloc 0
new
ih gerbil
ih bear
ih dolphin
rh dolphin
rh bear
rh gerbil

在 trace-01-ops.cmd 中看到的指令就是在這項測驗中，系統會嘗試輸入這些指令，並觀察程式行為是否符合預期。因此在讀入這些指令之後，script.py 會將這些指令當作是 qtest 的參數傳入並執行 qtest 已開始測試。

### Exception handling
在評分機制中， exception handling 非常的重要，因為使用者所撰寫的程式並不能保證不會有利外發生，如果每次例外發生時，程式都會崩潰，這樣這個評分機制就沒辦法為這些例外狀況做評分了。因此評分機制必須要確定例外發生時，程式仍然能正常運行，並且給予例外狀況扣分。

首先，最早看到 exception handling 相關程式碼是在 qtest.c 中。qtest 在初始時，會先設定好其 signal handler。

**qtest.c 中的 signal handler**

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

void sigalrmhandler(int sig)
{
    trigger_exception(
        "Time limit exceeded.  Either you are in an infinite loop, or your "
        "code is too inefficient");
}
static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

- SIGSEGV 負責處理 segmentation fault 的狀況，偵測使用者有沒有對非法記憶體進行存取。
- 當 segmentation fault 發生時，就會觸發 sigsegvhandler 並執行 trigger_exception。
- SIGALRM 負責監控 function 執行的時間，如果在給定時間內無法完成相關作業，就代表程式碼寫的不夠有效率。
- 當 timeout 發生時，就會觸發 sigalrmhandler 並執行 trigger_exception。
- timeout 長度是透過 harness.c 中的 exception_setup 函式做控制。

接著再來看看實際 signal handler 裡頭在做什麼，觀察 `exception_setup` 與 `trigger_exception`

**harness.c**

/*
 * Prepare for a risky operation using setjmp.
 * Function returns true for initial return, false for error return
 */
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;
    }
}

/*
 * Use longjmp to return to most recent exception setup
 */
void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

- exception_setup
- 透過 `sigsetjmp` 將 stack context 處存於變數 env 中。
- 透過 `alarm` 來決定 timeout 的時間。
- trigger_exception
- 接著當 exception 發生時，可以透過 `siglongjmp` 將 stack 的狀態還原到 exception 發生前，以避免程式崩潰。
- [$ man 3 sigsetjmp](https://linux.die.net/man/3/sigsetjmp)
- save stack context for nonlocal goto
- sigsetjmp() is similar to setjmp(). If, and only if, savesigs is nonzero, the process's current signal mask is saved in env and will be restored if a siglongjmp(3) is later performed with this env.

由此可知，`sigsetjmp` 與 `siglongjmp` 是用來避免例外處理造成程式崩潰的函式，因此會使用 `exception_setup` 與 `trigger_exception` 的部分就是在一些有可能會出現例外的地方，也就是我們所撰寫的函式。以下以 do_free 為例：

**qtest.c**

bool do_free(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    bool ok = true;
    if (q == NULL)
        report(3, "Warning: Calling free on null queue");
    error_check();
    if (qcnt > big_queue_size)
        set_cautious_mode(false);
    if (exception_setup(true))
        q_free(q);
    exception_cancel();
    set_cautious_mode(true);
    q = NULL;
    qcnt = 0;
    show_queue(3);
    size_t bcnt = allocation_check();
    if (bcnt > 0) {
        report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
               bcnt);
        ok = false;
    }
    return ok && !error_check();
}

qtest.c 中的 do_free 會在第 14 行呼叫我們所撰寫的 q_free，而系統要避免使用者 free 時造成例外發生，因此透過 `exception_setup` 與 `exception_cancel` 處理例外發生。當例外情況發生時，就會觸發上面所說的 sigalXXhandler ，再透過 `trigger_exception` 還原例外情況。

### heap 狀態檢查機制
heap 狀態檢查機制也是評分系統中重要的一部分，因為評分系統必須要知道 heap 的狀態，才能知道使用者所撰寫的程式碼操作 heap 的行為是否正確。

其相關機制於 **strdup 無法使用** 章節討論過了。

評分系統在 malloc 與 free 這兩個函式上面動了手腳，將他們替換為 `test_malloc` 與 `test_free`，他們利用一個 double linked-list 將 malloc 出去的 chunk 串起來，並且只將 chunk 中部分的空間作為原本使用者請求的空間返回給使用者。這樣的作法可以馬上掌握 heap 的狀態。
實際操作情況以上面的 do_free 為例，在第 20 行的地方，他執行了 allocation_check 去檢查 heap 是否有確實清空。

**harness.c**

void *test_malloc(size_t size)
{
    ...
    allocated_count++;
    return p;
}

void test_free(void *p)
{
    ...
    allocated_count--;
}

size_t allocation_check()
{
    return allocated_count;
}

allocation_check 其實就只是回傳 allocated_count 的值作為檢查的依據，而 allocated_count 在每次的 test_malloc 與 test_free 就會對該值做修改，以此實現 heap 狀態檢查機制。