Try   HackMD

2019q1 Homework1 (lab0)

contributed by < zodf0055980 >

tags: Linux 核心設計

開發環境

$ uname -a
Linux yuan-X555LF 4.15.0-45-generic 
$ gcc --version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

實作Queue要求

主要是去實作 FIFO & LIFO queue，需滿足以下功能:

  • q_new 去建立一個新的 Queue
  • q_free 把整個 Queue 所佔的記憶體給釋放掉
  • q_insert_head 在 head 插入 element
  • q_insert_tail 在 tail 插入 element
  • q_remove_head 從 head 移除一 element
  • q_size 回傳目前 Queue 的大小
  • q_reverse 把 Queue 反轉

2/26 簡化程式碼

queue_t

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

為了實現 q_insert_tail 和 q_size 的時間複雜度為

O(1) ，所以加入指向 Queue 尾端的 pointer 以及儲存 size 大小。

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return 0;
    q->size = 0;
    q->head = NULL;
    q->tail = NULL;
    return q;
}

這邊需要注意 malloc() 如果請求失敗，會回傳 NULL ，因此需要注意 malloc() 請求失敗的狀況。

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    int len = strlen(s) + 1;
    char *val = malloc(len * sizeof(char));
    if (!val) {
        free(newh);
        return false;
    }
    memset(val, 0, len);
    strncpy(val, s, len - 1);
    newh->next = q->head;
    newh->value = val;
    if (!q->head) { 
        q->tail = newh;
        q->head = newh;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    q->size++;
    return true;
}

這邊需注意 list_ele_t malloc() 成功，但 value malloc() 失敗，需要把 list_ele_t 給 free()，避免多餘的資料占用記憶體。
這邊也注意到自己的不足，居然把 sizeof(s) 當作整個 string 的長度，因為 s 是指標，所以得到的會是指標的大小，而非字串的長度。想起上課講到的，這是愚蠢的程式碼。
此段時間複雜度為

O(1)

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    // int len = sizeof(s) + 1;  // '/0' so +1
    int len = strlen(s) + 1;
    char *val = malloc(len * sizeof(char));
    if (!val) {
        free(newh);
        return false;
    }
    memset(val, 0, len);
    strncpy(val, s, len - 1);
    newh->value = val;
    newh->next = NULL;
    if (!q->head) {
        q->tail = newh;
        q->head = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;

    return true;
}

q_insert_tail 和 q_insert_head 相似，時間複雜度為

O(1)。

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    list_ele_t *nexte = q->head;
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, nexte->value, bufsize - 1);
    }
    q->head = q->head->next;
    free(nexte->value);
    free(nexte);
    q->size--;

    return true;
}

這邊需要注意 sp 需要判斷是否為 NULL，時間複雜度為

O(1)。

q_free

void q_free(queue_t *q)
{

    if (q) {
        list_ele_t *p = q->head;
        while (p) {
            list_ele_t *temp;
            temp = p;
            p = p->next;
            free(temp->value);
            free(temp);
        }
        free(q);
    }
}

這邊需要注意要先 free value，再free list_ele_t，時間複雜度為

O(n)。

q_size

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

這邊一開始沒有考慮 q 為 NULL 的狀況，時間複雜度為

O(1)。

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head || !q->head->next)
        return;
    list_ele_t *a = NULL;
    list_ele_t *b = q->head;
    list_ele_t *temp = q->head;

    while (b) {
        list_ele_t *c;
        c = a;
        a = b;
        b = b->next;
        a->next = c;
    }
    q->head = a;
    q->tail = temp;
}

這裡特地把以前資料結構的書給拿出來看，利用3個 pointer 去實現 Queue 的反轉。
這邊一開始測試檔一直過不了。

+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

參考學長的共筆紀錄

$ grep -rn 'Test of truncated strings'
traces/trace-06-string.cmd:1:# Test of truncated strings

並至 trace-06-string.cmd 中依序測試一遍，發現如果 Queue 未建立，會出現 Null Dereferencing。因此需判斷 Queue 中是否有多於兩個 element，而此 reverse 時間複雜度為

O(n)。

自動評分系統運作的原理

在 harness.h 中有這段

#define malloc test_malloc
#define free test_free

他把 malloc 和 free 都對應到 harness.c 中的程式碼，去做相關的檢查，這也是為什麼 segment fault 不會結束程式的原因。

struct BELE

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;

第一次看到宣告矩陣大小為0的，一查發現原來是 Arrays of Length Zero。透過去 malloc(sizeof(block_ele_t) + 額外的記憶體空間) 便可以利用 unsigned char payload[] 去對額外空間作存取。因此去利用 block_ele_t 去儲存有關分配記憶體的各項資料，去判斷是否有不正當得使用。

列出第一手資料，規格書或者編譯器使用手冊
:notes: jserv

以更正

test_malloc

block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
 *find_footer(new_block) = MAGICFOOTER;

利用 Arrays of Length Zero 的技巧把 new_block 指派我們想要 malloc() 的大小。並儲存分派記憶體大小和把 magic_header 設為 0xdeadbeef。以及利用 find_footer 去把 block_ele_t 最尾端指向 0xbeefdead。最後利用 double linked list 把分配的記憶體給串聯起來，並回傳實際可用空間的記憶體位址。
如果 test_malloc 成功執行，記憶體的內容會如下圖所示:


這樣便可以透過 magic_header 和 MAGICFOOTER 去判斷對記憶體的操作是否正確。而 magic_header 和 MAGICFOOTER 可為任意的值，主要是拿來判斷正確性。

test_free

因為 test_malloc 所回傳的值是實際可用空間的記憶體位址，因此需要透過 find_header 找 block_ele_t 所在的記憶體位址。

block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t));

並把 magic_header 和 MAGICFOOTER 指向 0xffffffff 來代表該記憶體區塊已經釋放，並用 FILLCHAR 去填滿。且從 double linked list 移除。

memset(p, FILLCHAR, b->payload_size);

single的操作

在 qtest 中的 queue_init() 中，透過

signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);

透過設置信號和 function，只要有 SIGSEGV 和 SIGALRM 的信號，便會執行 sigsegvhandler 和 sigalrmhandler 的 function。

而 SIGSEGV 負責處理的是 Invalid memory reference，一般我們程式如果發生 segmentation fault，便會產生 exception 通知 OS，由 OS 做處理。這也是為甚麼我們平常只要有 segmentation fault 程式就會中斷。而透過 signal() 去設定發生 segmentation fault 的處理 function，這也就是為什麼程式出錯而不會結束的原因。
而 SIGALRM 負責處理的是 Alarm clock。透過 alarm(time_limit) 去設定 timer 幾秒後產生 SIGALRM 的信號，alarm(0) 去取消停止當前的 timer 處理。

在 qtest.c 中對 Queue 的操作都有類似下面的 code:

if (exception_setup(true))
    q = q_new();
exception_cancel();

如果一段時間內(此程式為1秒)沒有執行 exception_cancel 去取消 timer 的處理，timer 會產生 Alarm clock 的信號，以確保程式不會有無窮迴圈的情況。

Reference

ktvexe 開發紀錄(lab0)

Last changed by 
 
吳宗遠
0
499
Published on HackMD