tags: `linux2019`

2019q1 Homework1 (lab0)

contributed by < ambersun1234 >

環境

$ uname -a
Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.11)

說明

題目摘要

實做一個可以支援 FIFO , LIFO 的 queue
在 queue.h & queue.c 中修改以下 function
- q_new: 新增一個空的 queue
- q_free: 釋出所有被 queue 使用的資源
- q_insert_head: 在 queue 的最前方新增一個新的資料( LIFO )
- q_insert_tail: 在 queue 的最後方新增一個新的資料( FIFO )
- q_remove_head: 移除最前方的資料
- q_size: 取得目前 queue 的資料數量
- q_reverse: 反轉 queue( 此 function 不應該新增或刪除任何 queue 裡面的資料 )

實驗紀錄

q_new













queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) {
        return NULL;
    } else {
        q->head = NULL;
        q->q_size = 0;
        q->last = q->head;
        return q;
    }
}

malloc 之後必須要確定是否成功，所以要檢查回傳值是否為 NULL

q_free















void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q != NULL) {
        list_ele_t *current = q->head, *next;
        while (current != NULL) {
            next = current->next;
            free(current->value);
            free(current);
            current = next;
        }
        free(q);
    }
}

q_insert_head





























bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    if (newh == NULL) {
        return false;
    } else {
        newh->value = strdup(s);
        if (newh->value == NULL) {
            free(newh);
            return false;
        }
        newh->next = q->head;  // newh->next will definitely be head

        if (q->head == NULL) {
            // queue empty
            q->last = newh;
        }
        q->head = newh;
        q->q_size++;
        return true;
    }
}

newh->value 我原本是用 malloc 的方式實做，但是在後來的 free 以及 quit 中都寫到說類似 ERROR: Freed queue, but 4 blocks are still allocated 的東西。因此我參考了 DyslexiaS 的開發紀錄，將 malloc 替換成 strdup 的方式實做才解決了問題
還有就是在將新的節點插入進 queue 的時候我使用了較多的 if else 判斷導致程式碼過於冗長，DyslexiaS 的開發紀錄也提供給我了一個另一種的解法，即將 newh->next 指向 q->head ( 因為 newh 必定會成為 queue 的第一個 )

q_insert_tail:









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

q_insert_tail 要求
$O (1)$ ，因此在 queue_t 中新增了 list_ele_t *last 用以紀錄當前 queue 中最後一個元素
































bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return false;
    }

    list_ele_t *newh;

    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    } else {
        newh->value = strdup(s);
        if (newh->value == NULL) {
            free(newh);
            return false;
        }
        newh->next = NULL;

        if (q->last == NULL) {
            q->head = q->last = newh;
        } else {
            q->last->next = newh;
            q->last = newh;
        }
        q->q_size++;

        return true;
    }
}

q_remove_head:


















bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->head == NULL) {
        return false;
    } else {
        if (sp != NULL) {
            strncpy(sp, q->head->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
        list_ele_t *temp = q->head;
        q->head = q->head->next;
        q->q_size--;
        free(temp->value);
        free(temp);
        return true;
    }
}

q_size:









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

為了達到
$O (1)$ ，我在 queue_t 中新增了 int q_size 紀錄了當前 queue 的 element 數量






int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return q->q_size;
}

q_reverse:























void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL) {
        return;
    }

    list_ele_t *previous = NULL, *current = q->head, *next = q->head;
    q->last = q->head;

    while (next != NULL) {
        // store
        next = current->next;

        // reverse
        current->next = previous;

        // move on
        previous = current;
        current = next;
    }
    q->head = previous;
}

自動評分系統運作的原理

根據 Makefile 的內容可以得知，自動評分系統是使用了 python 來進行評分的
最主要評分的 function 是 Tracer 裡面的 run & runTrace，評分的項目總共有15個，定義於 Tracer 裡面的 traceDict ; 其個別對應到的是 ./traces 的15個指令檔案

在 run 中是先做一些初始化設定，然後接著用一個 for 迴圈跑 traceDict 的 keys，之後在呼叫 runTrace








































def run(self, tid = 0):
    scoreDict = { k : 0 for k in self.traceDict.keys() }
    print("---\tTrace\t\tPoints")
    if tid == 0:
        tidList = self.traceDict.keys()
    else:
        if not tid in self.traceDict:
            print("ERROR: Invalid trace ID %d" % tid)
            return
        tidList = [tid]
    score = 0
    maxscore = 0
    if self.useValgrind:
        self.command = 'valgrind'
    else:
        self.command = self.qtest
        self.qtest = ''
    for t in tidList:
        tname = self.traceDict[t]
        if self.verbLevel > 0:
            print("+++ TESTING trace %s:" % tname)
        ok = self.runTrace(t)
        maxval = self.maxScores[t]
        tval = maxval if ok else 0
        print("---\t%s\t%d/%d" % (tname, tval, maxval))
        score += tval
        maxscore += maxval
        scoreDict[t] = tval
    print("---\tTOTAL\t\t%d/%d" % (score, maxscore))
    if self.autograde:
        # Generate JSON string
        jstring = '{"scores": {'
        first = True
        for k in scoreDict.keys():
            if not first:
                jstring += ', '
            first = False
            jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k])
        jstring += '}}'
        print(jstring)

runTrace 中使用了 subprocess.call 呼叫子行程用以執行各個 traceDict 的檔案，若子行程執行中出錯，則 retcode 就不是0













def runTrace(self, tid):
    if not tid in self.traceDict:
        print("ERROR: No trace with id %d" % tid)
        return False
    fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
    vname = "%d" % self.verbLevel
    clist = [self.command, self.qtest, "-v", vname, "-f", fname]
    try:
        retcode = subprocess.call(clist)
    except Exception as e:
        print("Call of '%s' failed: %s" % (" ".join(clist), e))
        return False
    return retcode == 0

最後評分是依據 runTrace 的回傳值來判斷要給幾分
```
tval = maxval if ok else 0
```
maxval 是各個項目的最高分 ( t 為當前 traceDict 的 key )
```
maxval = self.maxScores[t]
```

qtest的行為和技巧

qtest 實際上是透過一層包裝來呼叫 function( q_insert_head , q_insert_tail , q_reverse … etc. )，這些所謂的包裝是定義在 qtest.c裡面，如下所示









bool do_new(int argc, char *argv[]);
bool do_free(int argc, char *argv[]);
bool do_insert_head(int argc, char *argv[]);
bool do_insert_tail(int argc, char *argv[]);
bool do_remove_head(int argc, char *argv[]);
bool do_remove_head_quiet(int argc, char *argv[]);
bool do_reverse(int argc, char *argv[]);
bool do_size(int argc, char *argv[]);
bool do_show(int argc, char *argv[]);

而以上的這些 function 是以 function pointer 的形式透過 add_cmd() 儲存到 單向 linked list 裡面，linked list 的設計是為了方便使用者自行增加 function 到互動界面上

值得注意的是，在 harness.h 中有寫到
```
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
```
- 意思就是說，該程式將這些 function 改成自己的版本，這個大概也就可以解釋為什麼我嘗試要 malloc newh->value 的時候會有錯誤
- 更深入的閱讀程式碼之後我發現到，test_malloc 實際上是用一個更大的空間來儲存記憶體相關的東西，而且是使用 雙向 linked list 儲存
- 以下這個 struct 是用來儲存記憶體相關的東西
```
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;
```
  在 test_malloc 裡面有一句是這麼寫的
  block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));
  可以發現到除了 block_ele_t 之外還有 size 跟 sizeof(size_t)，其中 size 就是在 malloc 時的參數，另外一個是跟所謂的 magic number 有相關
  
  magic number: 程式設計中將一個數字寫死，用以表達特殊意義
  - 在 block_ele_t 中 magic_header 用以儲存此 struct 的記憶體狀態，回到真正 malloc 的地方，最後一個 sizeof(size_t) 即是要儲存 magic_footer 的
```
/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
```
  - test_malloc 的回傳值是定義成
    void *p = (void *) &new_block->payload;
    剛開始我很不明白為什麼是 payload ，而且他的大小還是0，後來有查到一個叫做 struct hack 的東西
    - cf. struct hack
      - 使用這個方法可以使 struct 達到動態記憶體分配
      - 在 struct 的最後新增一個大小為0的陣列
      - 然後在 malloc 的時候要求空間除了原本 struct 之外再加上額外需求空間
      reference struct hack
    - 以 struct hack 的方法即可以分配記憶體給 list_ele_t
  - 其中還有 static size_t allocated_count = 0; 用以紀錄目前 allocated 的記憶體數量

tags: linux2019

2019q1 Homework1 (lab0)

環境

說明

題目摘要

實驗紀錄

自動評分系統運作的原理

qtest的行為和技巧

Read more

2021q1 Homework1 (quiz1)

2020q1 Homework3 (quiz3)

2021q1 Homework4 (quiz4)

2020q1 Homework (期末專題)

tags: `linux2019`