Try   HackMD

2018q3 Homework2 (lab0)

tags: System-Software-2018

contributed by < DyslexiaS >

作業說明
C Programming Lab

git commit message 應該以動詞開頭,具體寫出做了什麼修改。如 "New Q" 這段訊息應改為 "Implement "
課程助教

實驗環境

$ uname -a
Linux dyslexia-E5-473G 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version 
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

更換遠端伺服器倉庫網址
將 git repository 的 https 改為 ssh,並且設定好 ssh-key,之後 git push 就不需要輸入帳號密碼

過程

queue_t data struct

由於 q_size 和 q_insert_tail 都要求

O(1) 的時間複雜度,因此需要隨時去紀錄 tail 和 size

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

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)); if (newh == NULL) return false; /* Don't forget to allocate space for the string and copy it */ /* What if either call to malloc returns NULL? */ newh->value = strdup(s); if (newh->value == NULL) { free(newh); return false; } if (q->head == NULL) q->tail = newh; newh->next = q->head; q->head = newh; ++q->q_size; return true; }

q_insert_tail

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 *newt = malloc(sizeof(list_ele_t)); if (newt == NULL) return false; else { newt->value = strdup(s); newt->next = NULL; q->tail->next = newt; q->tail = newt; ++q->q_size; return true; } }

q_free

  • 先把 element 清除乾淨才能 free 掉 queue
void q_free(queue_t *q) { /* How about freeing the list elements and the strings? */ /* Free queue structure */ if (q == NULL) return; while (q->head) { list_ele_t *tmp = q->head->next; free(q->head); q->head = tmp; } free(q); }

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; if (sp) { strncpy(sp, (q->head)->value, bufsize - 1); *(sp + bufsize - 1) = '\0'; list_ele_t *tmp = q->head; q->head = q->head->next; //free(tmp->value); free(tmp); --q->q_size; return true; } return false; }

strncpy description
Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

  • 在第 8 行的地方卡了很久,因為在做 strncpy 並沒有複製到 terminating null byte ('\0'),造成字串後面多了很多奇怪的東西,加上 '\0' 就解決了

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

  • 在第 11 行的地方,tmp->value 是由 strdup 在 free 掉 element 之前需要先 free 掉裡面的 value,但執行第 10 行卻會造成錯誤,後來發現有其他同學也遇到相同的狀況。
  • harness.h 有段 macro 會把 free 替換成自己的函式,因此我們所用的 free 不是真的 free
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • q_reverse

void q_reverse(queue_t *q) { /* You need to write the code for this function */ if (q == NULL || q->q_size == 0) return; list_ele_t *tmp = q->head->next; q->tail = q->head; while (tmp) { q->tail->next = tmp->next; tmp->next = q->head; q->head = tmp; tmp = q->tail->next; } }
  • 一開始想要用兩個 tmp 去紀錄當前的 node 以及 下一個 node,後來同學提醒可以用 tail->next 去紀錄,便能省去在創一個暫存的空間了
  • 一開始還把 node 數為 1, 2 的狀況獨立出來寫,但後來發現可以全部都使用同一個 while 來解決~

步驟

藍色箭頭為 node 指向位置
黑色箭頭才是 node->next
紅色箭頭為當次轉向的動作

  1. 將 tail 指向 head,所以現在 tail 和 head 都是第 1 個 node

  2. 將 tmp 賦值成 head->next (也就是第 2 個 node)

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  3. 開始做 while 迴圈,結束條件為 tmp == NULL,因此當節點只有 1 個時,便不會做以下步驟

  4. 將 tmp->next 存起來,才不會讓 a2 指向 a1 後,取不到 a3

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  5. 將 tmp(a2) 轉向,指到 a1

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

  6. 將 HEAD 和 tmp 往前推進

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →


  • 重複以上 step4 - step6
  • 跳出迴圈時,tmp 是 NULL, tail->next 也剛好是 NULL,因此也省掉手動把 tail->next 變成 NULL (一舉兩得
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 結束時
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

qtest 的行為和技巧

void *test_malloc(size_t size) <harness.h>

在 harness.h 裡有這麼一段 macro:

#define malloc test_malloc

因此我們使用 malloc 時,其實是用了 test_malloc,接著來看看 malloc 實際上會做什麼事情,以下以 doubly-linked list 來對 blocks 進行操作

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)); ... new_block->magic_header = MAGICHEADER; new_block->payload_size = size; *find_footer(new_block) = MAGICFOOTER; void *p = (void *) &new_block->payload; ...
static size_t *find_footer(block_ele_t *b)     
{
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    return p;
}

當我們 malloc 一個 list_ele_t 時,會被夾在 magic_header 和 find_footer 回傳的 footer 中間


其中unsigned char payload[0]; 是一不佔空間的變數(Struct Hack技巧),用來存 list_ele_t 的起始位置

GCC manual 6.17 : Arrays of Length Zero (Flexible array member)

  • 實際 malloc 的大小會是三塊加起來,MAGICHEADER, MAGICFOOTER 就是用來標記list_ele_t 邊界的紀錄點,因此在 test_free() 裡,footer != MAGICFOOTER 就會有 MSG_ERROR

Corruption detected in block with address %p when attempting to free it

C99 Flexible array member:

  • sizeof( ) 不可使用在incomplete type的變數上

  • 只可宣告為一個non-empty structure的最後一個成員

  • 因此以下的宣告方式都會造成編譯錯誤:

// Error: flexible array member in otherwise empty struct
struct line {
    char contents[];
};
// Error: flexible array member not at end of struct
struct line {
    char contents[];
    int length;
};

struct line {
        int length;
        char contents[];
};
 
struct lines {
        struct line l;
        int line_num;
};

以上 code 會有潛在的 stack smashing detected 問題

詳見

自動評分系統運作原理

GitHub