# 開發紀錄 lab(0) Queue 實作
Contributed by < [`dange0`](https://github.com/dange0) >
###### tags: `sysprog2018`
>兩個 commit message 都沒有具體說明做了哪些修改,請修正
>[name=課程助教][color=red]
>>已修正
>>[name=Dange0]
## 實驗環境
```shell
$ 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
```make
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
```bash
#!/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
```clike
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 一塊空間並放上欲複製的字串,再將其記憶體位置回傳。其看似美好的程式碼如下:
```clike
/* 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;
}
```
測試結果如下:
```shell
$ 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` 取代之。
```clike
newh->value = malloc(strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
strcpy(newh->value, s);
```
測試結果如下:
```shell
$ make test
...
--- TOTAL 100/100
```
推論成立!不過 `strdup` 到底哪裡錯了呢?在觀看完 [glibc](https://github.com/walac/glibc/blob/master/string/strdup.c) 中的 strdup 實做方式後,發現與自己手刻基本上沒有差異。其 `glibc/strdup.c` 相關程式碼如下:
```clike
__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**
```clike
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**
```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;
/*
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 行:
```clike=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`
```clike=32
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 的值。
```clike=
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;
}
```
執行結果:
```shell
$ 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 行如下:
```clike=17
if (sp != NULL) {
memset(sp+bufsize-1, '\0', 1);
strncpy(sp, del->value, bufsize - 1);
}
```
執行結果:
```shell
$ 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 依序往下輪替。
```clike
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;
}
```
實驗結果:
```shell
$ 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**
```python
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**
```clike
/* 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**
```clike
/*
* 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**
```clike=
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**
```clike
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 狀態檢查機制。