2019q1 Homework1 (lab0)

contributed by < ChihAnLin0607 >

C-programming lab摘要

連結：C-programming lab

練習目標

正確的記憶體管理
pointer-base資料結構的操作
字串的使用
利用資料結構中格外的資訊來加速某些關鍵動作的效能
建立能夠應付包含NULL之類非法輸入的系統

實作目標

最終目標為實作一個queue，結構示意圖如下：

不過整個程式結構已經完成，只需要修改、實作以下功能就可以：

q_new：創造一個空 queue。
q_free：釋放所有被 queue使用到的記憶體。
q_insert_head：嘗試將一筆資料放入 queue的最前面。
q_insert_tail：嘗試將一筆資料放入 queue的最後面。
q_remove_head：嘗試移除 queue的第一筆資料。
q_size：計算 queue內的資料數。
q_reverse：將 queue內的資料順序倒轉。這個函式不應該釋放或是新配置任何 queue內資料，他只是將現成的queue資料翻轉而已。

測試

make之後執行qtest，可以進到測試環境，輸入help可以查看可用指令，包含用new創立新的queue、ih插入資料到queue的頭等等。除此之外，也可以用make test讀取traces資料夾內預先些好的測試指令，進行測試並且評分。

Git

狀況一

當我push時，我發現我沒有在branch上面，如下方gitk的截圖：

原因：
是開發過程中(上圖中master位置的commit)，曾使用git checkout $（commit的SHA1）的方式切換到較早的commit，然後在用同方法切換回原本的commit。

而checkout到別的未被任何分支指向的commit時會出現以下訊息：

You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by performing another checkout.

If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -b with the checkout command again. Example:

  git checkout -b <new-branch-name>

HEAD is now at 4f6d494... Add x

簡單來說就是在告訴我，我正處於「斷頭(detached HEAD)」狀態，而斷頭是指當下這個 HEAD沒有指向任何的分支。換句話說，唯一的master分支是指向 commit message為''Implement Reverse''的commit，當我切換到之前的commit時，HEAD就離開了唯一的分支，造成斷頭狀態。另外值得一提的是，就算我是用 checkout $(commit的SHA1)的方式回到 master分支指向的 commit，git還是不會判定我離開斷頭狀態，雖然上方第一張圖看起來全部的commit都是在同一條線上，但其實邏輯上來說，master以上的是另外一個分支，如下方示意圖：

所以當時回到master分支的正確方式應該是要用git checkout master、用git checkout $(分支名稱)的方式回去才對。

解決：
其實解決辦法就在上方git的敘述中，我只需要在現在的位置建立一個暫時的新分支，然後跟 master分支做 merge，最後在刪除這個新分支就可以了。

$git checkout -b tmp_b
$git checkout master
$git merge tmp_b
$git branch -d tmp_b

最後成功的將master指向最新的commit了：

參考：

Queue的實作

queue_t

typedef struct {
    list_ele_t *head;
    /* new elements */
    list_ele_t *tail;
    int size;
    /****************/
} queue_t;

新增 tail指標指向 queue的最後一筆資料，這樣能讓q_insert_tail的時間複雜度為O(1)，只要直接對tail做操作就好。

size則是紀錄queue中資料的數量，為了是讓q_size的時間複雜度為O(1)。

q_insert_head

































bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    size_t s_size;

    // Return false if q is NULL
    if (!q)
        return false;

    // Allocate a new list_elet_t
    newh = malloc(sizeof(list_ele_t));
    if (!newh)  // Return false if malloc fail;
        return false;

    // Allocate the space for the string, and then copy s into it
    s_size = strlen(s);
    newh->value = malloc(s_size + 1);  // "+1" is for the last charactor '\0'
    if (!newh->value) {
        free(newh);
        return false;
    }
    memcpy(newh->value, s, s_size);
    newh->value[s_size] = 0;

    // Insert the new list_ele_t into q
    if (!q->head)
        q->tail = newh;
    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

在#16取得s的長度時，原本是用sizeof(s)來做取得，卻發現不管怎麼樣都是得到8，也就是s本身這個指標的大小，稍微整理一下後發現：

    char array[100];
    char ptr* = malloc(sizeof(char)*100);
    printf("%d\n", sizeof(array));    // 印出100
    printf("%d\n", sizeof(ptr));      // 印出8(64位元系統)

明明都是在sizeof內放一個指向一段記憶體空間的指標，為什麼一個就是得到該記憶體空間的大小，另一個就是得到該指標本身的大小呢？

為了釐清為什麼，我試著去查sizeof的定義，結果發現他並不是一個巨集甚至函式，他就跟加減乘除的符號一樣，對編譯器來說只是一個運算子，基本上他的值會在編譯階段被算出來(說基本上是因為C99新增了對動態宣告陣列做sizeof的功能)。

了解sizeof是什麼之後，我得到了以下的推測：回到上面的例子，在編譯階段時，因為array的空間是被靜態配置的，編譯器已經能夠確定他所佔用的記憶體空間，就能夠確定sizeof(array)為100；但是ptr指向的記憶體空間是動態配置的，在編譯階段無法確定他是否能夠成功利用malloc取得想要的記憶體大小，malloc也許會因為種種原因失敗，所以編譯器並無法確定ptr執行期間指向的記憶體大小為多少(甚至會不會指向記憶體位置都不確定)，只好退而求其次的將sizeof(ptr)算成ptr本身的大小。

過去總以為array和指標完全是同一件回事，原來在sizeof這件事上這兩者的行為並不一樣。

參考：sizeof- function or macro? [duplicate]

q_reverse






















void q_reverse(queue_t *q)
{
    function */
    if (!q || !q->size || q->size == 1)
        return;

    list_ele_t *prev = q->head, *curr = q->head->next, *next;

    q->head->next = NULL;
    q->tail = q->head;

    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    q->head = prev;

    return;
}

一、
#4原本是寫成下方這樣

    if (!q->size || !q)

結果測試發現如果q是NULL，就會跳出對NULL指標做操作的錯誤，但反過來寫成if (!q || !q->size)就沒有問題，這很明顯是因為在判斷||兩旁的expression時，會先判斷左邊的，如果他是True，才會在繼續判斷右邊的。

不過不放心還是去查了cppreference，也得到了證實確實如此，除了||，做&&運算時也是一樣，若左邊判斷為0，則右邊完全不會被計算。這稱為 short-circuit evaluation。

二、
一開始reverse採用的方式為，先建立一個長度和queue內資料數一樣的陣列，將queue內的資料按順序放入，然後在從array後方開始重新建立queue。

不過這樣會好需要 q->size的8倍的記憶體空間，在最後一項測試中，將會進行一個長度為2000000的queue反轉，這樣就需要16MB的記憶體空間，會產生「程式記憶體區段錯誤(core dump)」的錯誤。

研究了一下到底多少以上的記憶體空間才會造成區段錯誤，發現ulimit可以告訴我一些相關的資訊：

chihanlin@chihanlin-K55VM:~/linux_kernel/lab0-c$ ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
scheduling priority             (-e) 0
file size               (blocks, -f) unlimited
pending signals                 (-i) 31220
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) 819200
real-time priority              (-r) 0
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 31220
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

其中比較關心的是 stack size，其大小為8 MB。但首先要先確定動態配置的array其記憶體位置是放在stack中而不是heap中，所以做了以下的測試：

/* test.c */
void foo(int n)
{
    char array[n];
    printf("&a = 0x%X\n", &n);
    printf("array = 0x%X\n", array);
    printf("array+15 = 0x%X\n", array+15);

    char* ptr = malloc(16);
    printf("ptr = 0x%X\n", ptr);
    printf("ptr+15 = 0x%X\n", ptr+15);

}

int main()
{
    int n = 16;
    foo(n);
    return 0;
}

chihanlin@chihanlin-K55VM:~/linux_kernel/test$ ./a.out 
&a = 0x429D0F7C
array = 0x429D0F60
array+15 = 0x429D0F6F
ptr = 0x184A420
ptr+15 = 0x184A42F

知道foo的參數n會放在esp+4、也就是stack中；ptr指向一個用malloc配置的記憶體，然後malloc出的空間會配置在heap中。結果顯示array位置和n非常靠近，因此判斷動態配置的array仍然是放在stack中。

所以說若我的q_reverse若要求了16 MB，明顯超過ulimit -a告訴我的stack size 8 MB，一定會產生錯誤。

待解問題：

在foo函式用，n位置應該為esp+4，array長度為16，所以預期其位置應該在 esp-16，兩記憶體位置應該相差20，但結果顯示卻是28，直覺和 aligment有關，但還沒釐清。

自動評分系統

查看Makefile內的test命令：

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

driver

其程式內容摘要如下：


























































#定義class Tracer
class Tracer:

    # 定義變數member以及其初始值
    ...
    
    def __init__(...):
        
        # 建構子

        ...

    def runTrace(self, tid):
    
        # 用指定的trace進行測試
        # 若抓到exception就丟出訊息
        # 並且回傳false，否則回傳true

        ...
        
        try:
            retcode = subprocess.call(clist)
        except Exception as e:
            print("Call of '%s' failed: %s" % (" ".join(clist), e))
            return False
        return retcode == 0

    def run(self, tid = 0):
        # 若tid不為0，就只測試指定的trace
        # 若tid為0，則測試全部的trace
        # 若一開始的參數有--valgrind，則用valgrind ./qtest -v $(verblevel) -f $(trace file name)測試
        # 若沒有則用./qtest -v $(verblevel) -f $(trace file name)測試
        # 最後印出結果，如果一開始參數有-A，則把結果寫成json在印出來一次
        
        ...
        
def usage(name):

    # 印出可用信息

    ...

def run(name, args):
    
    # 判斷參數並做相對應的處理
    # -h       : 印出可用參數信息
    # -p PROG  : 待測試的程式
    # -t TID   : 用來測試的Trace ID
    # -v VLEVEL: 設定vervosity等級(0-3), levelFixed = Trus
    # -A       : autograde = True
    #宣告Tracer實體t，並執行t.run(tid)

    ...

if __name__ == "__main__":
    run(sys.argv[0], sys.argv[1:])

qtest

一、

在qtest中有以下程式碼：

    bool ok = true;
    ok = ok && run_console(infile_name);
    ok = ok && finish_cmd();
    return ok ? 0 : 1;

原本我來寫的話應該會寫成以下這樣：

    if(!run_console(infile_name) || !finish_cmd())
        return false;
    return true;

qtest中的程式碼利用 &&避開 if判斷式，我想可樣降低branch-miss的發生。

二、 Exception的處理

一開始就會先登入兩個 signal的信號處理函式：

static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler); //Signal Segmentation Violation
    signal(SIGALRM, sigalrmhandler); //限制程式時間用的
}

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

由上方程式碼看的出來，其實兩個信號處理函式都是呼叫trigger_excption，只是輸出的信息不一樣而已。

SIGALRM是由函式 alarm發出，當呼叫 alarm(n)的 n秒後，就會發出 SIGALRM信號。

qtest在進行任何 queue的操作(我們實作的內容)前，都會先呼叫 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;
    }
}

#3的sigsetjmp很重要，他能夠將當下的環境紀錄下來，並在其位置做個標記，供之後呼叫siglongjmp時能夠跳回該位置。另外當呼叫sigsetjmp的時候，他會回傳0，但如果是透過longjmp呼叫，他就會回傳一個非零的數字，所以上方#3和#15的 if els條件式就是利用此特性區分。

建立好環境紀錄後，如果有設置時間限制，也會呼叫 alarm(time_limit)，讓程式於time_limit秒後，發出SIGALRM，並丟出「ERROR: Time limit exceeded.」。

接下來以q_new當作例子：

bool do_new(int argc, char *argv[])
{
    // 先做參數檢查
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    
    //若q已存在，先將其釋放
    bool ok = true;
    if (q != NULL) {
        report(3, "Freeing old queue");
        ok = do_free(argc, argv);
    }
    error_check();
    
    // 將當前環境用sigsetjmp紀錄
    if (exception_setup(true))
        //執行new的實際操作
        q = q_new();
        
    // 取消alarm、禁止jmp等等
    exception_cancel();
    qcnt = 0;
    show_queue(3);
    return ok && !error_check();
}

exception_setup會在實際操作(q_new())之前被呼叫，他不但用sigsetjmp紀錄了當前環境，還根據 time_limit值設定了 alarm，所以若q_new的執行時間超過這個time_limit，就會丟出SIGALRM信號；或是q_new執行期間做了不正確的記憶體操作，就會出了SIGSEGV信號。不論是丟出哪個信號，因為之前queue_init有登入其相對的處理函式，所以會跳去執行trigger_exception：

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

如果之前已經有使用 siglongjmp的紀錄，那 trigger_exception就會呼叫siglongjmp跳回之前紀錄的點，也就是執行 q_new()前的exception_setup()中，然後使他回傳 false，跳過q_new()，然後從do_new()中回傳。

簡單來說qtest會在高風險程式執行前先紀錄位置，當該程式真的發生問題時，就jmp回紀錄的位置與環境，然後繞過有問題的程式繼續執行。

Valgrind

在進行較大筆資料的測試時(例如 trace-13-perf.cmd中的 ih doplhin 1000000)，使用Valgrind會丟出「ERROR: Time limit exceeded.」的錯誤，但是如果不用 Valgrind的話就不會。稍微查了一下，雖然 valgrind的使用不需要重新編譯，他會參雜新的指令到執行檔中，然後在一個虛擬的 CPU上面執行新程式碼，所以我猜這就是為什麼會造成時間過長的原因，因為多了許多valgrind的指令。

但還是要做記憶體檢查，所以決定將qtest中的時間限制加大，他的定義在 harness.c中，修改time_limit的值就可以增長時間限制了。

參考：Using and understanding the Valgrind core