2018q3 Homework2 (lab0)

contributed by <0xff07>

環境

uname -i:

Linux 4.15.0-34-generic x86_64 GNU/Linux

lscpu:

Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               70
Model name:          Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz
Stepping:            1
CPU MHz:             2289.664
CPU max MHz:         3700,0000
CPU min MHz:         800,0000
BogoMIPS:            4988.61
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
L4 cache:            131072K
NUMA node0 CPU(s):   0-7

cat /etc/lsb-release:

DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=18.04
DISTRIB_CODENAME=bionic
DISTRIB_DESCRIPTION="Ubuntu 18.04.1 LTS"

實作

queue_t

因為要求尾端插入與長度查詢的複雜度是

$O(1)$ ，因此在資料結構中加入 tail 與 size 分別紀錄尾端與長度:

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

q_free

void q_free(queue_t *q) 
{
    if (!q)
        return;
    list_ele_t *tmp = q->head;
    while (q->head) {
        tmp = q->head;
        q->head = q->head->next;
        if (tmp->value)
            free(tmp->value);
        if (tmp)
            free(tmp);
    }   
    if (q) 
        free(q);
}

若 head 為空，則顯然記憶體已經釋放。若 head 非空，則「釋放 head」可遞迴地視為「釋放串列第一個元素(迴圈中暫存於 tmp) ，並釋放剩下所有元素形成的串列(q -> head -> next)」 。

而再釋放串列中的元素之後，再釋放 q 即可。

若在 free 中傳入空指標，在測試程式中將出現 Attempt to free NULL 的錯誤訊息，並且扣分(儘管 man 中寫到傳入空指標是合法的)。因此這邊所有的 free 都事先檢測是否為空指標。

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh = NULL;
    char *_s = NULL;
    do {
        if (!q)
            break;
        newh = malloc(sizeof(list_ele_t));
        if (!newh)
            break;
        _s = malloc(strlen(s) + 1);
        if (!_s)
            break;
        strcpy(_s, s);
        newh->value = _s;
        newh->next = q->head;
        q->head = newh;
        if (!q->tail)
            q->tail = newh;
        q->size++;
        return true;
    } while (0);
    if (newh)
        free(newh);
    if (_s)
        free(_s);
    return false;
}

使用 do{...} while(0) 配合 break ，達到 goto 的效果，並進行各種例外處理。並在插入後，將屁股尾端維護好。正在思考例外處理與判斷的邏輯是否能夠更精減（立刻回去翻上週作業嗚嗚）。

另外發現若將 14. 15 行改成 cpumpound-literal 的寫法：

*new = (list_ele_t){.value=_s,.next=q->head};

在 git commit 時似乎會被檢查出 memory leak，跑出：

[queue.c:90]: (error) Memory leak: _s

Fail to pass static analysis.

但該作法可以順利通過 qtest 。因此不是很確定這種用法是否將造成 memory leak，或是有什麼潛在的不良影響。相關資料待查。

q_insert_tail

bool q_insert_tail(queue_t *q, char *s) 
{
    list_ele_t *newh = NULL;
    char *_s = NULL;
    do {
        if (!q)
            break;
        newh = malloc(sizeof(list_ele_t));
        if (!newh)
            break;
        _s = malloc(strlen(s) + 1); 
        if (!_s)
            break;
        strcpy(_s, s); 
        newh->value = _s; 
        newh->next = NULL;
        if (q->head)
            q->tail->next = newh;
        else
            q->head = newh;
        q->tail = newh;
        q->size++;
        return true;
    } while (0);
    if (newh)
        free(newh);
    if (_s)
        free(_s);
    return false;
}

大致上與前一個函數相同，紀錄尾端並在插入後維護好 tail 與 head 的指標。「新增 list_ele_t 」似乎可以寫成一個函式，但發現使用 strdup 時，即使 man 中提到：

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

即 strdup 中的記憶體由 malloc 配置，但使用 strdup 時測試程式，仍會判定沒有正確配置記憶體（見「其他」），因此尚未測試。

q_remove_head

依照要求，除了釋放記憶體，必要時得將節點中存的字串進行複製。因此照題目要求寫出來：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    list_ele_t *tmp = NULL;
    tmp = q->head;
    q->head = q->head->next;
    if (sp && tmp->value) {
        strncpy(sp, tmp->value, bufsize);
        sp[bufsize - 1] = 0;
    }
    q->size--;
    if (tmp->value)
        free(tmp->value);
    if (tmp)
        free(tmp);
    return true;
}

q_size

直接回傳存好的值大小：

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

q_reverse

假定

$L=[1,\dots ,k-1,k\dots ,n]$ ，則：

1. 若串列為空，或是串列僅有一個元素。則自己就是自己的反轉

2. 若已經有前

   $k$ 個元素反轉的串列
   $L^{\prime }=[k-1\dots 0]$:
   $$[k-1\dots 0]\cup [k,k+1\dots n]$$

   則將第

   $k$ 個元素加入反轉串列的頭部：
   $$[k,k-1\dots 0]\cup [k+1\dots n]$$

   就能構造出前

   $k+1$ 個元素反轉的串列。以此遞推下去。

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;
    if (q->head == q->tail)
        return;
    list_ele_t *buf[3] = {q->head, q->head->next, q->head->next->next};
    q->head->next = NULL;
    q->tail = q->head;
    while (buf[2]) {
        buf[1]->next = buf[0];
        buf[0] = buf[1];
        buf[1] = buf[2];
        buf[2] = buf[2]->next;
    }
    buf[1]->next = buf[0];
    q->head = buf[1];
}

前 2 個 if 敘述描述的是第 1. 中的狀況; 而其後的程式用於處理 2. 中的狀況。

我覺得這樣的實作看起來並不一目瞭然。似乎有待改進。

測試程式討論

記憶體管理

在 harness.[ch] 當中，可以看到記憶體管理相關的內容。該記憶體管理機制相關說明如下：

1. 將原先的 malloc 與 free 使用 test_malloc 與 test_free 取代。該部份可見 harness.h 最後面：

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

   所以實際上，在 queue.c 中呼叫 malloc 與 free 時，其實式分別呼叫 test_malloc 與 test_free 兩個函式。以下都用 test_malloc 與 test_free 稱呼該二函式（而不是 malloc 與 free）。

2. 所有因呼叫 test_malloc 得來的記憶體，實際上是紀錄在一個名為 allocated 的一個 doubly-linked list 中。該 linked list 結點的結構為 block_ele_t，定義在 harness.c 中：

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

   在這個結構體中，最後一個成員 payload[0] 是實際給呼叫者使用的記憶體開頭。該成員使用到的 GCC 中 "Array of Length Zero" 。該功能簡便處在於：若結構體中的最後一個成員是大小為 0 的陣列，那麼可以透過 malloc(sizeof(block_ele_t) + 希望 payload 後面接著多少記憶體) 來達成「最後一個成員大小可以任意指定」的效果（另外一個好處是 malloc 跟 free 一次就可以完成，不用替 payload 開頭的記憶體再 malloc 一次）。malloc_test 中可以發現以下程式：

   ​​​​void *test_malloc(size_t size)
   ​​​​{
   ​​​​    if (noallocate_mode) {
   ​​​​        report_event(MSG_FATAL, "Calls to malloc disallowed");
   ​​​​        return NULL;
   ​​​​    }
   ​​​​    if (fail_allocation()) {
   ​​​​        report_event(MSG_WARN, "Malloc returning NULL");
   ​​​​        return NULL;
   ​​​​    }
   ​​​​    block_ele_t *new_block =
   ​​​​        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
   ​​​​    ...
   

   這個技巧表現在程式的 malloc(size + sizeof(block_ele_t) + sizeof(size_t)) 當中。但除了 sizeof(block_ele_t) 與 size 之外， 還多了一個 sizeof(size_t) 的大小。這是因為使用者實際可使用的記憶體，前後被兩個 size_t 整數包著，裡面各自紀錄著兩個 Magic Number，作為驗證這塊記憶體是否是由 test_malloc 分配的依據，以及作為記憶體是否有產生越界等不佳使用的依據。

3. 位於記憶體之前的 magic number，實際上就是結構體中 magic_header 這個成員，其值會在 test_malloc 中被指定為 MAGICHEADER，也就是 0xdeadbeef ; 在記憶體尾端的 size_t 整數，數值必定為 MAGICFOOTER，也就是 0xbeefdead。

4. 因為要回傳給使用者的指標實際上是 payload 的位置，因在程式中另外有 find_footer 跟 find_header 這兩個函式作為輔助。前這傳入 block_ele_t* ，回傳位於 payload 尾端 magic number 的位址。如 test_malloc 中有一段指定尾端 magic number 的程式：

   ​​​​*find_footer(new_block) = MAGICFOOTER;
   

   而後者則是傳入使用者呼叫後得到的記憶體開頭，反推該記憶體所屬的 block_ele_t 的開頭位置。這兩個函式除了用在 test_malloc 當中，也會用再 test_free 當中。在呼叫 test_free 時，使用者傳入的，實際上是 payload 的位置，但釋放記憶體時，除了該記憶體之外，該記憶體所屬的結構體，也要一併釋放。因此需要有一個尋找該記憶體所屬開頭的方法。

   該二函數的原理不難理解。給定 block_ele_t，尾端的 magic number，由 payload_size 進行推算即可; 對於反推記憶體所屬的結構體，則是利用 sizeof(block_ele_t) 反推，並且尋找反推過後的記憶體是否在 allocated 的清單中。若沒有，則推論為錯誤的配置。

   而在 find_header 中有檢測傳入指標是否為空的設定。

   我懷疑這是一個不能使用 calloc 跟 strdup 的理由。但目前還沒確認該二函數中的 malloc 是否有被影響到。

5. test_free 中用的原理類似：首先用 find_header 找出使用者準備釋放的記憶體，其所屬的結構體有沒有再 allocated 裡面。若傳入的指標為空指標，或是該記憶體不屬於任何一個節點，find_header 內部會分別傳出「試圖釋放空指標」或「記憶體損壞」等警告。

6. 若順利找到該記憶體所屬的節點，接著檢驗尾端的 magic number 是否仍為 MAGICFOOTER，作為記憶體有沒有被越界存取等狀況的判斷依據。若比對結果發現不合，也會發出該區段記憶體損壞的警告。

7. 若確認結果無誤，則將記憶體區段前後的 magic number 都設成 MAGICFREE。並且將記憶體內容都用 FHILLCHAR 填充。最後移出 allocated 這個 doubly-linked list。

   不確定為什麼要先把 magic number 都改掉之後再釋放。我猜測是同樣大小的記憶體如果又被 malloc ，但裡面仍有 magic number 時，會造成誤判，以為不合法的記憶體其實是合法的。

8. 在分配記憶體時，每呼叫一次 test_malloc ，allocate_count 就會 +1; 而每呼叫一次 test_free ，該數值就會 -1。因此程式即將結束時，判斷該數值，即可知道是否有妥當地釋放記憶體。

例外處理

在 harness.c 中，有一些使用 sigsetjmp, siglongjmp 的函式作為例外處理。該函式並未在 harness.c 中被其他函式呼叫。因此推測該例外處理用在其他地方。

shell 實作

思考

1. 雖然過了 qtest，但應該要更有「品味」一點。決定再把上週的東西仔細看一遍，並嘗試影片裡面的技巧。
2. 程式要怎麼做到「發現記憶體有沒有正確釋放」或「檢查有沒有在不該使用 malloc 的時候使用 malloc」是一件很神奇的事，決定好好研究一下。

其他

無法使用 calloc 及 strdup

使用 strdup 或 calloc 的話，測試程式會頻繁地跑出如：

CMU 助教為了測試使用 macro 將 malloc 和 free 替換成 test_malloc 和 test_free , 請看 harness.h 和harness.c, 所以你用其他配置記憶體的函數測試程式沒辦法正確測試
amikai

...
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
ERROR: Attempted to free unallocated block.  Address = 0x55772899ccf0
ERROR: Attempted to free unallocated or co：rrupted block.  Address = 0x55772899ccf0
ERROR: Corruption detected in block with address 0x55772899ccf0 when attempting to free it
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (1 failures total)
ERROR: Attempted to free unallocated block.  Address = 0x55772899cc90
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x55772899cc90
ERROR: Corruption detected in block with address 0x55772899cc90 when attempting to free it
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (2 failures total)
free(): invalid next size (fast)
---	trace-01-ops	0/6
...

以及非常低的分數。後來在 qtest.c 中才發現：

/* Our program needs to use regular malloc/free */

雖然說明中有提及： " The function must explicitly allocate space and copy the string into it."，但不是很確定要求「明顯」到什麼程度。以至於花費不少時間懷疑人生。

free

依照 man 中的內容：

The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc(), or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no operation is performed.

因此若 ptr 為 NULL，則 free(ptr) 應該要合法。但以下實作:

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh = NULL;
    char *_s = NULL;
    do {
        if (!q)
            break;
        newh = malloc (sizeof(list_ele_t));
        if (!newh)
            break;
        int len = strlen(s);
        _s = malloc(len + 1); 
        if (!_s)
            break;
        ...
    } while (0);
    free (newh);
    free (_s);
    return false;
}

在測試時將會出現如:

+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
Attempt to free NULL
Attempt to free NULL
---	trace-07-robust	0/7

的錯誤訊息。