Try   HackMD

2018q3 Homework2 (lab0)

contributed by < ChingChieh >

tags: sysprog2018

開發紀錄

環境

  • 系統版本:unbuntu 18.04.1
  • gcc 版本:gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

過程

queue_t

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

因為 q_insert_tailq_size 要達到

O(1) 所以需要額外記住 queue size 和 tail 位子


q_size

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 == NULL || q->head == NULL) {
        return 0;
    }   
    return q->size;
}

q_free

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

要記得先free(q->head->value)再free(q->head)
因為我一開始就沒有用strdup的方式複製字串,所以沒遇到free(q->head->value)會錯誤的問題


q_insert_head

bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; /* What should you do if the q is NULL? */ if (q == NULL) { return false; } newh = (list_ele_t *) malloc(sizeof(list_ele_t)); if (newh == NULL) { return false; } size_t s_len = strlen(s) + 1; // Don't forget the \0!!!!!!! /* Don't forget to allocate space for the string and copy it */ newh->value = (char *) malloc(s_len * sizeof(char)); if (newh->value == NULL) { free(newh); return false; } strcpy(newh->value, s); /* What if either call to malloc returns NULL? */ newh->next = q->head; if (newh->next == NULL) { // Change the tail q->tail = newh; } q->head = newh; q->size++; return true; }

要記得malloc的時候要多給他一個 char 的空間存 '\0'


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; newt = (list_ele_t *) malloc(sizeof(list_ele_t)); if (newt == NULL) { return false; } long int slen = strlen(s) + 1; newt->value = (char *) malloc(sizeof(char) * slen); if (newt->value == NULL) { free(newt); return false; } strcpy(newt->value, s); if (q->tail != NULL) { q->tail->next = newt; } else { q->head = newt; } q->tail = newt; newt->next = NULL; q->size++; return true; }

q_remove_head

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

q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size < 2) {
        return;
    }
    q->tail = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *temp;
    list_ele_t *curr = q->head;
    while (curr != NULL) {
        temp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = temp;
    }
    q->head = prev;
}                                             

進度

$ make test
scripts/driver.py
...
...
---	trace-15-perf	7/7
---	TOTAL		100/100

makefile

  • rm *~ 意思
    • 把檔案結尾是~的檔案刪掉,這種檔案是 editor 產生的備用檔。如果在 .vimrc 設定set backup也可以產生這種備用檔

遭遇問題

  1. [queue.c:79]: (error) Memory leak: newh
    • 原因:當要對 queue 做 insert 的時候總共要 malloc() 兩次,如果回傳結果是 NULL 就 return false,但在第二次檢查的時候忘記把第一次 malloc() 的空間 free 掉
newh = (list_ele_t *) malloc(sizeof(list_ele_t)); if (newh == NULL) { return false; } newh->value = (char *) malloc(s_len * sizeof(char)); if (newh->value == NULL) { free(newh); //要記得 free 掉之前成功 malloc 的空間 return false; }

自動評分系統運作原理

qtest行為&技巧

用有沒有 define INTERNAL 來判斷是否使用自定義的malloc和free

在 harrness.h 裡面有

#ifdef INTERNAL
...
#else
#define malloc test_malloc
#define free test_free
#endif                

帶表如果有先定義INTERNAL就不會把 malloc、free 改成 test_malloc、test_free


如何偵測buffer overflow

test_malloc 程式碼:

void *test_malloc(size_t size) { ... block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t)); if (new_block == NULL) { report_event(MSG_FATAL, "Couldn't allocate any more memory"); error_occurred = true; } new_block->magic_header = MAGICHEADER; new_block->payload_size = size; *find_footer(new_block) = MAGICFOOTER; void *p = (void *) &new_block->payload; memset(p, FILLCHAR, size); new_block->next = allocated; new_block->prev = NULL; if (allocated) allocated->prev = new_block; allocated = new_block; allocated_count++; return p; }

每次呼叫test_malloc(size)分配的空間:

malloc(size + sizeof(block_ele_t) + sizeof(size_t));

test_malloc return 的是指向size起始address的pointer:

void *p = (void *) &new_block->payload;

這裡用到的技巧是arrays of length zero,通常是用在struct的最後一個element,這樣的好處是可以把payload當成block_ele_t後面記憶體位址的開頭


此外再用find_footer()定出size結尾的記憶體位址,然後把後面那塊sizeof(size_t)記憶體的值改成MAGICFOOTER

static size_t *find_footer(block_ele_t *b) 
{
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    //payload_size 是使用者可以用的空間大小
    return p;
}

*find_footer(new_block) = MAGICFOOTER;

加上之前把magic_header的值設成MAGICHEADER,所以使用者能合法使用的空間就像被兩塊記憶體空間夾在中間,使用超出size的空間就會改到MAGICFOOTER或MAGICHEADER因此可以在test_free時被偵測出來