Try   HackMD

2019q1 Homework1 (lab0)

contributed by < yiwei01 >

tags: sysprog2019

Development environment

$ uname -a
Linux yiwei-X550JX 4.15.0-45-generic #48-Ubuntu SMP Tue Jan 29 16:28:13 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc--version
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

lab0 requirement

  • q_new: Create a new, empty queue.
  • q_free: Free all storage used by a queue.
  • q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
  • q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
  • q_remove_head: Attempt to remove the element at the head of the queue.
  • q_size: Compute the number of elements in the queue
  • q_reverse: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.

How to achieve lab0 requirement step by step

Data structure design

To meet the requirement that q_insert_tail and q_size operate in time O(1), I add list_ele_t *tail and int size fields in queue_t structure in queue.h.






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

q_new

Allocate memory to new queue. If malloc dose not return NULL, then initialize the queue and return its starting address, else return NULL.











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

q_size

By adding int size field in queue_t structure, q_size can operate in time O(1).

Problems encountered and solved :
I forget to check NULL pointer which result in NULL pointer dereference. Hence, I add a NULL pointer check when returning the value.





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

q_insert_head

Before inserting new element, check if queue exists and can allocate enough space. In addition, I use additional variable unsigned int len_s to record the length of s in case that s is NULL but be taken as input of strlen. When copying string, I use strncpy and assign '\0' to the last address of (newh->value). At the end, update q->head and q->size (and q->tail if needed).

Problems encountered and solved :
I misuse strcat(newh->value,"\0") to add terminating character after strncpy(newh->value, s, len_s);. However, strcat overwrites the terminating null byte ('\0') at the end of dest, so if there is not terminating character in dest, it may has unexpected garbled message in it.































bool q_insert_head(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    unsigned int len_s = !s ? 0 : strlen(s);
    newh->value = malloc((len_s + 1) * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }

    strncpy(newh->value, s, len_s);
    (newh->value)[len_s] = '\0';
    newh->next = q->head;

    q->head = newh;
    if (!q->tail) {
        q->tail = newh;
    }
    q->size++;
    
    return true;
}

q_insert_tail

Almost as same as q_insert_head, the subtle difference is that q_insert_tail has to check if q->tail exists. If q->tail exists, assign new list element to q->tail->next. At the end, update q->tail and q->size (and q->head if needed).



































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

    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (!newt) {
        return false;
    }   

    unsigned int len_s = !s ? 0 : strlen(s);
    newt->value = malloc((len_s + 1) * sizeof(char));
    if (!newt->value) {
        free(newt);
        return false;
    }   

    strncpy(newt->value, s, len_s);
    (newt->value)[len_s] = '\0';
    newt->next = NULL;

    if (q->tail) {
        q->tail->next = newt;
    }   
    q->tail = newt;

    if (!q->head) {
        q->head = newt;
    }
    q->size++;

    return true;
}

q_remove_head

First, check if there are elements in q can be removed. Second, copying string from q->head->value to sp. Third, use additional variable list_ele_t *tmp to record q->head then remove tmp->value and tmp. At the end, update q->size.

After applying cppcheck, I'm reminded that "Unsigned variable 'bufsize' can't be negative so it is unnecessary to test it." So, I remove unnecessary assertion in Line 3.























bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    assert(bufsize >= 0); /* This line is removed 
                             after applying cppcheck */
    if (!q || !q->head) {
        return false;
    }   

    if (sp && q->head->value) {
        unsigned int copy_len = bufsize > 0 ? bufsize - 1 : 0;
        strncpy(sp, q->head->value, copy_len);
        sp[copy_len] = '\0';
    }   

    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;

    return true;
}

q_free

Use list_ele_t *ptr to record current q->head and an additional variable list_ele_t *tmp to record ptr->next, after ptr->value and ptr are freed, assign tmp to ptr before go on next iteration. At the end, free q.
















void q_free(queue_t *q)
{
    if (!q) {
        return;
    }

    for (list_ele_t *ptr = q->head; ptr;) {
        list_ele_t *tmp = ptr->next;
        free(ptr->value);
        free(ptr);
        ptr = tmp;
    }

    free(q);
}

q_reverse

If queue is not NULL, use list_ele_t *prev to record the previous list elment and list_ele_t *next to record the next element. Then reverse links by assigning prev to curr->next.



















void q_reverse(queue_t *q)
{
    if (!q) {
        return;
    }

    list_ele_t *prev = NULL, *next = NULL;
    list_ele_t *curr = q->head;

    q->tail = q->head;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    q->head = prev;
}

Learning GNU/Linux development tools

perf

Problem encountered ( Installation ) :
$ cat /proc/sys/kernel/perf_event_paranoid return 3
solved by :
$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"
or

sudo sysctl kernel.perf_event_paranoid=1

How to improve performance

透過 perf ，我發現我的 q_reverse 算是整支程式的 bottleneck
Todo : 想改進方式

Samples: 3K of event 'cycles:ppp', Event count (approx.): 2894699324
Overhead  Command    Shared Object       Symbol                                                                  ◆
  19.12%  qtest      libc-2.27.so        [.] _int_malloc                                                         ▒
  12.55%  qtest      qtest               [.] q_reverse                                                           ▒
   7.56%  qtest      qtest               [.] test_free                                                           ▒
   7.23%  qtest      libc-2.27.so        [.] cfree@GLIBC_2.2.5                                                   ▒
   5.88%  qtest      libc-2.27.so        [.] malloc                                                              ▒
   5.13%  qtest      qtest               [.] find_footer                                                         ▒
   4.95%  qtest      qtest               [.] test_malloc                                                         ▒
   2.71%  qtest      libc-2.27.so        [.] __memset_avx2_unaligned_erms                                        ▒
   2.71%  qtest      [kernel]            [k] 0xffffffff86d8bf47                                                  ▒
   2.01%  qtest      qtest               [.] find_header                                                         ▒
   1.88%  qtest      qtest               [.] q_insert_head                                                       ▒
   1.86%  qtest      libc-2.27.so        [.] __random_r    
   ...

How automatic scoring system works

Behavior and skills in qtest

0xff07 同學的筆記已紀錄的很完整，自己理解過後再整理一次重點：

  1. programmer 呼叫的 malloc 已被替換成 test_malloc
  2. programmer 呼叫的 free 已被替換成 test_free
  3. programmer 呼叫的 strdup 已被替換成 test_strdup

資料結構圖示：

  • block_ele_t :
    • struct BELE *next : 指向 allocated(doubly linked list) 的下一個 node
    • struct BELE *prev : 指向 allocated(doubly linked list) 的上一個 node
    • size_t payload_size : 紀錄 programmer 呼叫 malloc 時要求的大小
    • size_t magic_header : 用以驗證這塊 allocate 出去的 block 是否還合法
    • unsigned char payload[0] : 真正能讓 programmer 使用的空間。
      • 其為 Arrays of Length Zero 的用法，其特徵為 : 當 zero-length array 是 structure 中的最後一個 member 時，則呼叫 malloc(sizeof( structure ) + 指定大小)時，該 structure 中的 zero-length array 得到的可用空間即為指定大小。觀察 harness.c，可發現在 test_malloc 中便利用了此特性。
      ​​​​​​​​block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));
      size : programmer 呼叫 malloc 時要求的大小( payload )
      sizeof(size_t) : 額外給 magic_footer 的空間。
      • 註 : block_ele_t 裡的 magic_header 與 magic_footer 皆是用來驗證這塊 block 是否還合法。在 test_malloc 中初始 magic_header 的值為 0xdeadbeef ， magic_footer 的值為 0xbeefdead，因此若該 block 的 magic_header 或 magic_footer 的值被更改，則代表此塊 block 曾被非法存取。

回傳 header 與 footer 的位址，其中 find_header 會檢查傳入的 block 是否真的是 allocated block，並檢查 magic_header 是否被更改過

test_malloc

檢查現在是否為可分配的模式、此次分配是否成功、是否擁有足夠空間滿足使用者的要求，若成功則分配空間給使用者，並會在 block 紀錄分配多大的大小、初始 magic_header 與 magic_footer，最後加入 allocated 這個 doubly linked list

test_free

檢查現在是否為可分配的模式、欲 free 的空間是否為 NULL、magic_footer 是否被更改過，若通過上述檢查，則將 payload 以 FILLCHAR 來覆蓋，並將 magic_header、 magic_footer assign 為 MAGICFREE，最後移出 doubly linked list

test_strdup

將 strdup 會呼叫到的 malloc 替換為呼叫 test_malloc.

Last changed by 
 
yi wei Wang
0
454
Published on HackMD