2019q1 Homework1 (lab0)

contributed by < rebvivi>

tags: linux2019

• C Programming Lab
• F01: lab0

作業要求

• FIFO 和 LIFO 實作 queue
  我們是用 linked list 來實現

  • queue_t：queue 的基本架構
  • q_size：計算 queue 中有幾個 element
  • q_new：新增一個 empty 的 queue
  • q_free：清除整個 queue
  • q_insert_head：使用 LIFO 的方法新增 element
  • q_remove_head：移除 queue 的第一個 element
  • q_insert_tail：使用 FIFO 的方法新增 element
  • q_reverse：把 queue 裡面的 element 反轉

• 解釋自動評分系統運作的原理以及提及 qtest 的行為和裡頭的技巧

• 所需要的 C 語言認知 :

  • Explicit memory management, as required in C.
  • Creating and manipulating pointer-based data structures.
  • Working with strings.
  • Enhancing the performance of key operations by storing redundant information in data structures.
  • Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

不要過度簡化作業要求，明明 CMU lab0 要求很多，為何你只看到這句話？工程人員實事求是的精神去哪了？及早脫離「文組^TM」

jserv

開發環境

$ uname -a
Linux peiwen-X550VX 4.18.0-15-generic #16~18.04.1-Ubuntu SMP Thu Feb 7 14:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

實作

基本的程式碼架構老師已經都建好了，必須先了解 linked list 以及 queue 的架構才能實作

queue_t

queue 的基本架構

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    size_t size;
} queue_t

新增 size 讓 queue 隨時紀錄現在 queue 的大小，
不用從頭到尾跑一遍才能知道 queue 的大小

q_size

計算 queue 中有幾個 element

int q_size(queue_t *q)
{
    if (q == NULL || q->size == 0) {
        return 0;
    } else {
        return q->size;
    }
}

因為 queue_t 有新增 size 的 index，讓 q_size 的時間複雜度能維持在

$O(1)$

q_new

新增一個 empty 的 queue

queue_t *q_new()
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));

    if (q != NULL) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}

要注意 malloc 有沒有配置到記憶體

q_free

清除整個 queue

void q_free(queue_t *q)
{
    if (q != NULL) {
        list_ele_t *temp;

        while ((q->head) != NULL) {
            temp = q->head;
            q->head = temp->next;
            free(temp->value);
            free(temp);
        }
    }
    free(q);
    return;
}

記得要先把 element 的 value free 掉之後才能 free 掉 element，
最後再釋放 queue 之前配置的記憶體。

q_insert_head

使用 LIFO 的方法新增 element

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newnode = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newnode == NULL) {
        return false;
       // free(newnode);
    }

    if (q->size == 0) {
        q->tail = newnode;
    }
    newnode->value = strdup(s);
    newnode->next = q->head;
    q->head = newnode;
    q->size++;

    return true;
}

過程中犯的錯誤

第 7 行的 if ，如果已經判斷 newnode == NULL ，再 free(newnode) 的話 ，會出現以下的錯誤

Attempt to free NULL

每次 malloc 都要確認有沒有配置到記憶體，如果配置失敗就要回傳 false 並且 free 剛才 malloc 的東西，避免產生 memory leak 的問題

如果一開始 queue 的 size 是 0 的話，記得要調整 tail

q_remove_head

移除 queue 的第一個 element

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || (q->size) == 0) {
        return false;
    }
    list_ele_t *remove;
    remove = q->head;
    q->head = q->head->next;

    if (sp != NULL) {
        memset(sp, '\0', bufsize);
        strncpy(sp, remove->value, bufsize - 1);
    }
    free(remove->value);
    free(remove);
    q->size--;
    return true;
}

記得要 free 第一個 element 的 value 再 free 掉 element

q_insert_tail

使用 FIFO 的方法新增 element

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }

    list_ele_t *newinsert = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newinsert == NULL) {
        return false;
    }

    newinsert->value = strdup(s);
    newinsert->next = NULL;
    if (q->size == 0) {
        q->head = newinsert;
    }
    q->tail->next = newinsert;
    q->tail = newinsert;
    q->size++;
    return true;
}

每次 malloc 都要確認有沒有配置到記憶體，如果配置失敗就要回傳 false 並且 free 剛才 malloc 的 node，避免產生 memory leak 的問題

如果一開始 queue 的 size 是 0 的話，記得要調整 head

過程中犯的錯誤

除了 malloc newinsert 之外， newinsert 的 value 也要配置記憶體

newinsert->value = malloc(strlen(s) + 1);

第 12 行使用到 strdup()， 但是會造成 memory allocate 的錯誤
strdup()不是標準的 C 函式，在 strdup() 的 Linux Man Page 的 Description 中提到：

The strdup() function returns a pointer to a new string
which is a duplicate of the string s.
Memory for the new string is obtained with malloc(3),
and can be freed with free(3).

我們在 queue.c 所呼叫的 malloc 和 free 在 qtest 都會改成呼叫 test_malloc 和 test_free，所以如果我們使用 strdup()，就用不到真正的malloc 和 free，導致配置記憶體出問題

而 strcpy() 是標準的 C 函式，所以應該改成：

strcpy(newinsert->value, s);

「strdup()不是標準的 C 函数，所以在 linux 上使用會有問題」這句陳述的「所以」有問題，GNU/Linux 是符合 POSIX 標準的作業系統，語言標準 (如 C99) 和標準執行環境 (如 POSIX) 之間的關聯，你需要描述。請查證並列出 POSIX.1-2001 規格書描述。在你「舉燭」之前，要讀書。

function 用於數學領域，譯作「函數」，但在程式設計中作為通用 subroutine 的話，譯作「函式」

jserv

q_reverse

把 queue 裡面的 element 反轉

void q_reverse(queue_t *q)
{
    list_ele_t *current = NULL;
    list_ele_t *before = NULL;
    list_ele_t *nextnode;
    if (q != NULL && q->size > 1) {
        current = q->head;
        q->tail = current;
        while (current != NULL) {
            nextnode = current->next;
            current->next = before;
            before = current;
            current = nextnode;
            q->head = before;
        }
        return;
    }
}

如果 queue 是空的或是 queue 只有一個 element 就不用 reverse

---

自動評分系統運作的原理

harness.[ch]

在 harness.h 中，我們在 queue.c 所用的 malloc和 free
都被改成呼叫 test_malloc 和 test_free

/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free

block_ele_t 是一個 doubly linked list 的結構

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 實際上需要配置的空間＝
(我們所要求的 size 大小) + (block_ele_t 所需要的空間) + (sizeof(size_t)的空間)，而 sizeof(size_t) 的空間是為了紀錄 magic_footer

magic_header 和 magic_footer是用來紀錄所配置的記憶體的前後位置，我們將兩者定義為常數

/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead

如果magic_header 和 magic_footer的數值被更改了，代表我們寫入的位址超過我們配置記憶體的範圍
如果是magic_header被更動數值，就是寫入的記憶體向前超過我們配置的範圍，如果是magic_footer被更動數值，就是寫入的記憶體向後超過我們配置的範圍

Q&A
Q：為什麼當初宣告block_ele_t的 structure 的時候不宣告 magic_footer？

A：因為我們每次用 malloc 所輸入的 size 都不一樣，所以配置空間的結尾
也會不同，magic_footer 位置也就不同，所以我們ㄧ要幫magic_footer預留一個sizeof(size_t)的空間，之後再用find_footer去找到magic_footer的位置

需要解釋 magic 的用途，最好搭配用另外一個獨立的試驗 (及相關記憶體分析工具) 來說明，避免「舉燭」。

jserv

test_malloc 所配置的空間紀錄在叫做allocated的 doubly linked list中，這個 doubly linked list中的 payload[0]代表我們在 queue.c 用 malloc呼叫的記憶體的開頭

用 allocate_count紀錄所配置的記憶體長度，如果沒有歸還完全 malloc所配置的記憶體，allocate_count的長度就會大於 1 ，並且出現以下的錯誤訊息

"ERROR: Freed queue, but %lu blocks are still allocated"

void *test_malloc(size_t size)
{
    ...
    
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    
    ...
    
    void *p = (void *) &new_block->payload;
   
    ...
    
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

exeption 處理

exception 的設置目的：

• 如果程式超過 limit_time ，就會發出錯誤訊息

在處理 exception 的時候用到了 sigsetjmp ，如果 sigsetjmp的值不是 0 ，代表是從 siglongjmp 回來的

setjmp() and sigsetjmp() return 0 if returning directly, and nonzero when returning from longjmp(3) or siglongjmp(3) using the saved context

而 siglongjmp 不 return，在 siglongjmp的 Linux Man Page 的 Return Value 有提到：

These functions never return.

主要概念

如果 limit_time=true，代表程式是有時間限制的，如果在時間限制內沒有呼叫 exception_cancel的話，就會觸發 trigger_exception 產生錯誤訊息

在 qtest 中我們都把 exception_setup 中的 limit_time 設成 true

• 因為並不是從 setlongjmp 跳回來的，所以sigsetjmp的值是 0
• 跳到 exception_setup 的 17 行執行，此時 jmp_ready = true ， 而 time_limited 最初設定是 false ，現在被改成 time_limited = true
• 因為 jmp_ready = true 所以執行trigger_exception第 6 行的 siglongjmp
• 此時因為是從 setlongjmp 跳回來的，sigsetjmp 的值變成不是 0 ，所以會執行 exception_setup的第 3 行的 if 的內容
• jmp_ready = false ， time_limited 從 true 被改成 false，report_event 產生錯誤訊息

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

void exception_cancel()
{
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    jmp_ready = false;
    error_message = "";
}

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

console.[ch]

在 console.h 中，command 和 parameter 都是一個 linked list 的結構
我們利用 add_cmd和add_param來將 command 和 parameter 加入 linked list

//command
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

//parameter
typedef struct PELE param_ele, *param_ptr;
struct PELE {
    char *name;
    int *valp;
    char *documentation;
    /* Function that gets called whenever parameter changes */
    setter_function setter;
    param_ptr next;
};

在 console.c 中，有一個 linked list 的結構用來儲存 input

#define RIO_BUFSIZE 8192
typedef struct RIO_ELE rio_t, *rio_ptr;
struct RIO_ELE {
    int fd;                /* File descriptor */
    int cnt;               /* Unread bytes in internal buffer */
    char *bufptr;          /* Next unread byte in internal buffer */
    char buf[RIO_BUFSIZE]; /* Internal buffer */
    rio_ptr prev;          /* Next element in stack */
};

parse_args把所有的 input 都轉換成 (int argc, char *argv[]) 的形式，將所有的 input 都用同一種形式存取，這樣對於呼叫任意 qtest 中的函式也會更加方便

char **parse_args(char *line, int *argcp)
{
    ...
	
    *argcp = argc;
    return argv;
}

qtest

在console_init裡頭，設定輸入 input 和測試函式的連結
例如：輸入 input "new"，會執行測試函式"do_new"測試我們在 queue.c 中所打的 q_new

static void console_init()
{
    add_cmd("new", do_new, "                | Create new queue");
  
    ...
}