Try   HackMD

開發紀錄 lab(0) Queue 實作

Contributed by < dange0 >

tags: sysprog2018

兩個 commit message 都沒有具體說明做了哪些修改，請修正
課程助教

已修正
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 中的 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(

n2)

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
    • 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 狀態檢查機制。

Last changed by 
 
Dange
0
1
489
Published on HackMD