2019q1 Homework1 (lab0)

contributed by < evanjack2002 >

tags: linux2019

F01: lab0

作業要求

• 在 GitHub 上 fork lab0-c
• 詳細閱讀 C Programming Lab
  • 依據指示著手修改 queue.[ch] 和連帶的檔案
  • 用 Git 管理各項修改
  • 務必詳閱 如何寫好 Git Commit Message
• 除了修改程式，也要編輯「作業區」，增添開發紀錄和 GitHub 連結，提及如何逐步達到要求，以及如何改善效能
  • 解釋自動評分系統運作的原理
  • 提及 qtest 的行為和裡頭的技巧
• 截止日期：Mar 3, 2019 (含) 之前

詳細閱讀 C Programming Lab

Knowlege base

1. C programming
2. Linked lists
3. Asympotic (big-Oh) notation
4. Linux Man pages

Overview

The queue contents are represented as a singly-linked list, with each element represented by a structure of type list_ele_t, having fields value and next, storing a pointer to a string and a pointer to the next list element, respectively.

Programming Task

Your task is to modify the code in queue.h and queue.c to fully implement the following functions.

• q_new:Create a new, empty queue.
• q_free:Free all storage used by a queue.
• q_inserthead:Attempt to insert a new element at the head of the queue (LIFO discipline).
• q_inserttail:Attempt to insert a new element at the tail of the queue (FIFO discipline).
• q_removehead:Attempt to remove the element at the head of the queue.
• q_size:Compute the number of elements in the queue.
• q_reverse:Reorder the list so that the queue elements are reversed in order. This function should notallocate or free any list elements (either directly or via calls to other functions that allocate or free listelements.) Instead, it should rearrange the existing elements.

Two of the functions: q_insert_tail and q_size will require some effort on your part to meet therequired performance standards. We require that your implementations operate in time

$O(1)$.

解釋自動評分系統運作的原理

• 透過 driver.py python script，呼叫 subprocess.call 去執行 qtest ，並使用 qtest 的參數 -f 來輸入測試項目的檔案。

  ​​​​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)
  

• 共15個測試項目 trace-01~15，前5個項目各6分，後10個項目各7分，透過 qtest 執行成功與否累加積分，總分100。

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

  ​​​​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
  

  ​​​​$ tree ./traces/
  ​​​​./traces/
  ​​​​├── trace-01-ops.cmd
  ​​​​├── trace-02-ops.cmd
  ​​​​├── trace-03-ops.cmd
  ​​​​├── trace-04-ops.cmd
  ​​​​├── trace-05-ops.cmd
  ​​​​├── trace-06-string.cmd
  ​​​​├── trace-07-robust.cmd
  ​​​​├── trace-08-robust.cmd
  ​​​​├── trace-09-robust.cmd
  ​​​​├── trace-10-malloc.cmd
  ​​​​├── trace-11-malloc.cmd
  ​​​​├── trace-12-malloc.cmd
  ​​​​├── trace-13-perf.cmd
  ​​​​├── trace-14-perf.cmd
  ​​​​├── trace-15-perf.cmd
  

提及 qtest 的行為和裡頭的技巧

• 透過建立 cmd linked list，根據 cmd 執行對應的 operation，如： ih command 的operation 為 do_insert_head()。

  ​​​​add_cmd("ih", do_insert_head, ...);
  

  ​​​​while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
  ​​​​    next_cmd = next_cmd->next;
  ​​​​if (next_cmd) {
  ​​​​    ok = next_cmd->operation(argc, argv);
  

• 透過 exception_setup(true) 與 exception_cancel() ，實做執行時間超過 time_limit 的 exception。

  ​​​​if (exception_setup(true))
  ​​​​    rval = q_remove_head(q, removes, string_length + 1);
  ​​​​exception_cancel();
  

  • exception_setup(true)
    • 用 sigsetjmp 建立返回 jump 點。
    • 並啟動 alarm(time_limit) timer。
  • sigalrmhandler
    • 如果 alarm timer 到期，會觸發 SIGALRM signal。
    • 註冊對應 SIGALRM 的 signal handler 為 sigalrmhandler。
    • sigalrmhandler 會呼叫 siglongjmp，做 "nonlocal goto" 到之前建立的 jump 點。
  • exception_cancel()
    • 如果執行的 function（e.q. 上面的 q_remove_head())，在沒有超過 time_limit 時，執行到 exception_cancel()。
    • exception_cancel() 會設定 alarm(0) 來停止 alarm timer。

• 透過 Preprocesser，替換 malloc() 和 free()。

  ​​​​#define malloc test_malloc
  ​​​​#define free test_free
  

  • 透過替換 malloc 的 test_malloc，來做很多應用。
    • 如讓 option malloc xx command，使 malloc() 有機率回傳 NULL 要不到記憶體配置的狀況。
      ​​​​​​​​​​​​static bool fail_allocation()
      ​​​​​​​​​​​​{
      ​​​​​​​​​​​​    double weight = (double) random() / RAND_MAX;
      ​​​​​​​​​​​​    return (weight < 0.01 * fail_probability);
      ​​​​​​​​​​​​}
      

實做

q_new()

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
        return NULL;

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free()

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *e;

    if (!q)
        return;

    while (q->head) {
        e = q->head;
        q->head = q->head->next;
        free(e->value);
        free(e);
    };
    free(q);
}

q_insert_head()

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    unsigned int len;

    /* What should you do if the q is NULL? */
    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    memset(newh, 0, sizeof(*newh));
    len = strlen(s);
    newh->value = malloc(sizeof(char) * (len + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }

    if (q->head == NULL) {
        q->tail = newh;
    }
    strcpy(newh->value, s);
    newh->value[len] = '\0';
    newh->next = q->head;
    q->head = newh;
    q->size++;
    return true;
}

q_insert_tail()

In time

$O(1)$

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 */
    list_ele_t *e;
    unsigned int len;

    if (!q)
        return false;

    e = malloc(sizeof(list_ele_t));
    if (!e)
        return false;

    len = strlen(s);
    e->value = malloc(sizeof(char) * (len + 1));
    if (!e->value) {
        free(e);
        return false;
    }

    strcpy(e->value, s);
    e->value[len] = '\0';
    e->next = NULL;
    q->tail->next = e;
    q->tail = e;
    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. */
    unsigned int len;
    list_ele_t *e;

    if (!q || !q->head)
        return false;

    e = q->head;
    q->head = q->head->next;
    if (q->head == NULL)
        q->tail = NULL;
    if (sp) {
        memset(sp, 0, bufsize);
        len = strlen(e->value);
        if (bufsize > len + 1)
            strcpy(sp, e->value);
        else
            strncpy(sp, e->value, bufsize - 1);
    }
    free(e->value);
    free(e);
    q->size--;
    return true;
}

q_reverse()

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    list_ele_t *e = NULL;
    list_ele_t *rh = NULL; /* reverse head */

    if (!q || !q->head)
        return;

    while (q->head) {
        e = q->head;
        q->head = q->head->next;
        if (rh == NULL) {
            rh = e;
            rh->next = NULL;
            q->tail = rh;
        } else {
            e->next = rh;
            rh = e;
        }
    }
    q->head = rh;
}

q_size()

In time

$O(1)$

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

    return q->size;
}

structure queue_t

/* Queue structure */
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
                      */
    list_ele_t *tail;
    unsigned int size;
} queue_t;

疑問

valgrind: qtest valgrind_existence
	$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
	cp qtest $(patched_file)
	chmod u+x $(patched_file)
	sed -i "s/alarm/isnan/g" $(patched_file)

• sed -i "s/alarm/isnan/g" $(patched_file) 用於在 binary 裡，替換 alarm 文字成 isnan 文字，是為了讓 valgrind 不會有 alarm timer 中順利進行。
• 但不懂為何這樣可行？

Note

• sigsetjmp and siglongjmp man page

  ​​​​#include <setjmp.h>
  
  ​​​​int setjmp(jmp_buf env);
  ​​​​int sigsetjmp(sigjmp_buf env, int savesigs);
  
  ​​​​void longjmp(jmp_buf env, int val);
  ​​​​void siglongjmp(sigjmp_buf env, int val);
  

  • The functions described on this page are used for performing "nonlocal gotos": transferring execution from one function to a predetermined location in another function.
  • sigsetjmp() and siglongjmp() also perform nonlocal gotos, but provide predictable handling of the process signal mask.

• Linux 核心設計 (Spring 2019) 進度表

參考資料應該列出「第一手材料」

jserv

謝謝老師，我在去找找。

• Linux 核心設計: 第 1 週發展回顧
• apt install build-essential git-core cppcheck clang-format valgrind