2019q1 Homework2 (lab0)

contributed by < GOGOGOGOGOGOG>

Overview

• 前置作業
  -關於git以及關於git以及clang的設定與安裝
  -關於Linklist

• 測試環境

• 作業要求

• 作業說明

  • queue.h
  • q_new
  • q_size
  • q_free
  • q_insert_head
  • q_insert_tail
  • q_reverse
  • q_remove_head
  • 現況

• 自動評分系統

前置準備：關於git以及clang的設定與安裝

• clang安裝
  首先將clang進行安裝，安裝指令sudo apt install clang-format 安裝之後queue.c檔進行format，否則無法編譯，利用 clang-format -i queue.c分別將queue.c檔以及queue.h檔進行format。
• git操作與指令
  首先將作業進行 fork，點選左上角的 fork 圖示後，利用mkdir <folder>開啟一個新的資料夾後，cd <folder>進入該資料夾並寫入指令git clone <https://github.com/GOGOGOGOGOGOG/lab0-c.git>把　repositories　拉到你的系統中，https://github.com/GOGOGOGOGOGOG/lab0-c.git 這段網址是你的repository。
  而在開啟檔案之前，git init必須先進行，修改完之後，在儲存該程式碼的資料夾中打入git add . 將全部檔案都加入到要上傳的地方後，接著輸入git commit -m "what you have done"。
  第一次push東西上去，在push時需要明確打出要上傳的位置及初始化該branch，輸入指令git push --set-upstream origin master 並打入git push輸入帳號名稱和密碼後即可上傳，在上傳過程中要特別注意branch名稱和上傳的位置，否則會有下列狀況：

error: src refspec homework does not match any.
error: failed to push some refs to 'https://github.com/GOGOGOGOGOGOG/lab0-c.git'

鍵入完成會出現以下畫面

Enumerating objects: 13, done.
Counting objects: 100% (13/13), done.
Delta compression using up to 4 threads
Compressing objects: 100% (7/7), done.
Writing objects: 100% (7/7), 2.25 KiB | 1.12 MiB/s, done.
Total 7 (delta 5), reused 0 (delta 0)
remote: Resolving deltas: 100% (5/5), completed with 5 local objects.
To https://github.com/GOGOGOGOGOGOG/lab0-c.git
   67654f5..47a5b2a  master -> master

安裝若有問題可以參考以下網址：https://stackoverflow.com/questions/4181861/src-refspec-master-does-not-match-any-when-pushing-commits-in-git

• （10/4更新）

  關於重新上傳更改後的資料到github上：

  本次在作業上進行修改後，一開始不知道如何直接上傳新的檔案至github上，只能被動的github上修改queue.c的方程式，詢問過同學後，terminal端輸入 git add . 後打入git commit -m "Modefiedchange queue.c" 要打入修改了哪些東西和第一個字要大寫，否則會出現系統不斷要求你重新commit的情況。如下：

• Separate subject from body with a blank line
  Proceed with commit? [e/n/?] e
  commitmodified q_free [line 1]
• Capitalize the subject line
  test access=NULL; [line 2]
• Separate subject from body with a blank line
  Proceed with commit? [e/n/?] e
  commitmodifiedabout queue.c [line 1]
• Capitalize the subject line
  Proceed with commit? [e/n/?] e
  Mergedmodifiedq_free queue.c [line 1]
• Use the imperative mood in the subject line, e.g 'fix' not 'fixes'

輸入完正確指令後會出現：

Commitmodifiedq_free queue.c
1 file changed, 5 insertions(+), 1 deletion(-)

也可以用git log 和 git status 來確認上傳狀況。

前置準備：Linklist

在大學時期由於修課的關係，並不常接觸c語言，對於結構也不是很了解也不知道linklist，於是曾經看過以下的影片和書籍

• https://www.youtube.com/watch?v=NobHlGUjV3g&index=3&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
• https://www.youtube.com/watch?v=A5_XdiK4J8A&index=24&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
• c語言教學手冊
• c語言規格書
  經由c語言規格書我們可以了解到對於struct的定義：

A struct in the C programming language (and many derivatives) is a composite data type (or record) declaration that defines a physically grouped list of variables to be placed under one name in a block of memory, allowing the different variables to be accessed via a single pointer, or the struct declared name which returns the same address. The struct data type can contain many other complex and simple data types in an association, so it is a natural type for organizing mixed-data-type records such as lists of hard-drive directory entries (file length, name, extension, physical (cylinder, disk, head indexes) address, etc.), or other mixed-type records (patient names, address, telephone... insurance codes, balance, etc.). 

亦即我們可以透過 struct來組合兩個完全不同的型態，而透過利用malloc函式來進行動態記憶體的配置，malloc函式會回傳所配置的記憶體位址，所以必須以一個指標變數來接收它。因為指標變數會有它所指向的型態，因此我們把malloc函式所傳回的位址先進行型態轉換，再把它設給指標變數存放。如果配置失敗，則malloc函式傳回NULL。而本次的作業的header檔裡可以發現，本次有兩個結構，其結構變數分別是：list_ele_t和queue_t。我的解讀和編排是，本次作業分成大結構與小結構，小結構（list_ele_t）用來表示輸入的字串和指向下一個的位址，而大結構（queue_t）則用來表示輸入的字串所形成的小結構之排頭和排尾以及總字串大小。

測試環境

＄cat /proc/version
NAME="Ubuntu"
VERSION="16.04.5 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.5 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial
＄ cat /proc/version
Linux version 4.15.0-34-generic (buildd@lgw01-amd64-037) (gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10)) #37~16.04.1-Ubuntu SMP Tue Aug 28 10:44:06 UTC 2018

作業要求

詳看：http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf

• 重要訊息

These are combined to implement a queue of strings, as illustrated in Figure 1. The top-level representation of a queue is a structure of type queue_t.  In the starter code, this structure contains only a single field head, but you will want to add other fields. The queue contents are represented as a singly-linked list, with each element represented by a structure of type list_ele_t, having fields value and next, storing a pointer to a string and a pointer to the next list element, respectively.  The final list element has its next pointer set to NULL. You may add other fields to the structure list_ele_t, although you need not do so

裡面提到我們可以自由添加變數。

作業說明

queue.h

首先針對 queue.h 一開始我們必須先設定我們的全域變數：

typedef struct ELE {
    /* Pointer to array holding string.
       This array needs to be explicitly allocated and freed */
    char *value;
    struct ELE *next;
} list_ele_t;

由註解我們可以得知需要一個指標陣列來儲存字串和一個指標來儲存下一個字串的位址。
而在大結構中：

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
    /*
      You will need to add more fields to this structure
      to efficiently implement q_size and q_insert_tail
    */
} queue_t;

我們由註解可以得知，需要一指標tail和表示字串大小size。

q_new

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q!=NULL) {
        q->head =NULL;
         q->tail = NULL;
        q->size = 0;
    }
    return q;
}

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 */
    return (q!=NULL) ? q->size : 0;
}

其中return的語法為：若q不為NULL則查看qsize0，否則直接判定為0。

q_free

void q_free(queue_t *q)
{
 if (q == NULL)
        return;

    list_ele_t *access = q->head;  //將access指向qhead

    while (access != NULL) {  //檢查access是否為NULL
        q->head = access;
        access = access->next;
        
        free(q->head->value);
        
        
        free(q->head);
        q->size--;
    }

access=NULL;
free(q);
}

其方法為用while迴圈查看所有的字串和節點並將其刪除。但似乎有些東西尚未清無乾淨(bcnt)？，使用gdb下去看q_free函式。

(10/6更新)後來發現free本身並沒有問題，問題是出現在sizeof和strlen的用法，前者會造成qtest的do_insert_head中q-_insert_head會回傳false

於是我做了一個實驗，在insert_tail打入strlen而在insert_head裡保持原樣，結果顯示前者的回傳值為true，後者為false

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
   list_ele_t *ptr;
    if (q == NULL)
        return false;

    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    newh->value = (char *) malloc(
        strlen(s) + 1);  //因為s是從0開始要加一才能表示其真正所需的記憶體
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);  //將接受的字串指標s傳入newh的value中
    s = NULL;


    ptr = q->head;     //將前一個結構位址儲存在ptr中
    newh->next = ptr;  //將新創的結構指向之前生成的結構

    if (q->size == 0) {
        q->tail = newh;
    }



    q->head = newh;  // newh所存的位址指派給q的head中
    q->size++;

    return true;
}

（10/10更新）

關於sizeof和strlen的相關問題可以參考這篇，修改成strlen後，qtest為滿分： https://read01.com/zh-tw/4ezR.html#.W8iLDRR2TCI

回傳的為一個指標s和一個結構指標，而所接受的字串也為一個指標陣列，為了將接受的字串傳入newh的value中我使用了strcpy函式，但在這之前，其實在一開始我是使用strdup的，但後來出現了一些問題，這裡我會在q_insert_tail做解釋以及參考了[pjchiou]同學的為何不能使用strdup。

q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    
   // list_ele_t *ptr2=q->tail;

    if (q == NULL)
        return false;

    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    newh->value = (char *) malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    s = NULL;

    newh->next = NULL;
    if (q->size != 0) {
        q->tail->next = newh;
        // ptr2->next = newh;
    } else {
        q->head = newh;  //把newh的位址傳給qhead

        newh->next = NULL;
    }
    q->tail = newh;
    q->size++;

    return true;

    // if (newh != NULL) {
    // newh->next = q->head;
    // newh->value = strdup(s);}
}

這裡一開始我的想法同樣和insert head一樣給予一個指標變數暫存原先的tail指標，但後來經過詢問同學後，發現其實這麼做只會浪費記憶體空間和降低效率而已。然而後來我原本是使用strdup（如下面註解）但總是會有segamation fault的情況發生，為了觀察這種狀況，我參考網路上關於linux系統除錯（http://www.cnblogs.com/panfeng412/archive/2011/11/06/2237857.html）
在參考下，我使用了gdb以及core文件，透過man 7 signal，我們發現其默認的handler會在出現Segmentation Fault時打印出core文件，以此來觀察其位址哪裡出錯。
首先我們給core文件一個記憶體 ulimit -c 1024 並且告至他在出錯時產生文件./segfault3 其執行畫面如下圖：

在圖形中core文件告訴我insert tail和free以及reverse等地方出現了corrupted block，經過參考了[pjchiou]同學的共筆後，查了一下c語言規格書，發現關於strdup的定義

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在複製字串的同時，會自動產生一個記憶體給新建立的位址，我懷疑是在釋放記憶體的時候沒有手動的釋放那些記憶體，再加上strdup在harness.c 會被看成一個自定義的函式。也就是說使用 strdup ，就會變成在用 malloc 與 test_free 便會自動偵錯。另外參考網路上的一些見解，strdup本身是一個不是一個標準的c函式，所以linux系統會自動偵錯。(待確認)

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || q->size == 0)
        return;

    list_ele_t *last = NULL;
    list_ele_t *current;
    q->tail = q->head;

    while (current != NULL) {
        current = q->head->next;
        q->head->next = last;
 
        last = q->head;
       
        q->head = current;
        
    }
    q->head = last;
}

（）裡的編號是執行的順序
A B C表示位址

head: A–->B(2)–->C(5)–->NULL–->C

tail: A

last: NULL–->A(1)–->B(4)–->C(7)

current: B–->C(3)–->NULL

方法是先將q->tail和q->head都指向q->head，透過while迴圈一個結構一個結構改變指向的方向，最後再將last的位址指派給q->head，因為last經過while迴圈後最後的儲存位址為原本的最後一個結構，最後將q->head指派成最後一個結構，即完成reverse。

q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    // if queue is NULL or empty
    if (q == NULL || q->size == 0)
        return false;

    int size;
   
    if (sp != NULL) {
        size = strlen(q->head->value);
        if (size > bufsize - 1) {
            size = bufsize - 1;
        } else {
            size = size;
        }

        strncpy(sp, q->head->value, size);
        sp[size] = '\0';
    }


    list_ele_t *tmp1 = q->head;


    q->head = q->head->next;
    q->size--;

    free(tmp1->value);
    free(tmp1);

    return true;
}

這裡的想法是：先處理關於刪減掉頭結構後，size會減少的情況，首先定義size的大小，將value指派給size。接下來考慮到除去頭後，size減少的情況。
接著開始清除head資料，首先將q->head儲存到一個指標變數中，接著把下一個結構的位址指派給q->head，定義為新的q->head，然後釋放移除的記憶體。

現況：

改動後為100分

剩下7分實在不確定是哪裡出了問題，透過gdb和core tmp只可以看出是在執行qtest的時候，free函式出現了memory leak，原因待查詢，避免時間來不及先研究自動評分系統。（10/4）

了解自動評分系統（10/4）

• cmd各自是執行什麼？
• q_free函式的呼叫

首先來看qtest.c裡面的程式碼，可以發現do_new 的布林運算對應到的是執行q_new 函式，而do_free 對應的是執行q_free函式等等…
而在static void console_init() 是對於各個cmd進行定義和宣告，也增加了錯誤提示訊息等等… 而其中最讓我好奇的便是 在do_free進行宣告的bcnt和allocation_check()，似乎被扣7分的原因在於我的bcnt為清除乾淨，向學長討教後，發現所謂的bcnt指的是block count，也代表有暫存的記憶體並沒有清除乾淨，於是我決定再用gdb進行觀測，順便了解這次的評分機制。
首先我們將qtst進行gdb檢測並且在do_free進行break，如圖：

可以看到後來的數據逐一印出後，基本上都沒什麼問題，直到進入 bcnt的那一行程式碼，如圖：

重新在進行測試一次：

可以看到即使經過q_free後，我們的記憶體依舊沒有清除乾淨，這讓我懷疑是不是自己的q_free的程式邏輯出了一點問題，決定之後再來好好檢查看看。除此之外可以看到有一個trigger_exception( "Time limit exceeded. Either you are in an infinite loop, or your " "code is too inefficient"); 這是一個測試程式執行時間的函式，在這個函式中只要接收到signum 的訊號時就會執行底下的handler 函式。在qtest.c裡面可以看到：

/* Signal handlers */
void sigsegvhandler(int sig)
{
    trigger_exception(
        "Segmentation fault occurred.  You dereferenced a NULL or invalid "
        "pointer");
}

void sigalrmhandler(int sig)
{
    trigger_exception(
        "Time limit exceeded.  Either you are in an infinite loop, or your "
        "code is too inefficient");
}


static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

提問

使用strdup和 strcpy

將原程式碼改為：

bool q_insert_head(queue_t *q, char *s) {
  list_ele_t *ptr;
  if (q == NULL)
    return false;

  list_ele_t *newh = (list_ele_t *)malloc(sizeof(list_ele_t));
  if (newh == NULL)
    return false;

  //newh->value = (char *)malloc(
      //strlen(s) + 1);
    newh->value = (char *)malloc(
      strlen(s)+ 1 ); //因為s是從0開始要加一才能表示其真正所需的記憶體
  if (!newh->value) {
    free(newh);
    return false;
  }
  newh->value=strdup(s); //將接受的字串指標s傳入newh的value中
  s = NULL;
  
  ptr = q->head;    //將前一個結構位址儲存在ptr中
  newh->next = ptr; //將新創的結構指向之前生成的結構

  if (q->size == 0) {
    q->tail = newh;
  }

會出現core dump的錯誤，不太確定是因為strdup不是c語言標準函式而在harness.c裡被看成一個自定義的函式而出錯？
harness.c:

if (!found) {
      report_event(MSG_ERROR,
                   "Attempted to free unallocated block.  Address = %p", p);
      error_occurred = true;
    }
  }

在qtest.c中的memset函式：

為什麼在 do_remove_head 中會使用到memset？ 其使用的目的是什麼？
又為什麼 do_remove_head_quiet 並沒有使用到呢？

 memset(removes + 1, 'X', string_length + STRINGPAD - 1);
  removes[string_length + STRINGPAD] = '\0';

使用gdb來看memset:

13 = 0x60da31 'X' <repeats 200 times>…看不懂是什麼意思？

c語言規格書中的 memset ：

  memset - fill memory with a constant byte

SYNOPSIS
       #include <string.h>

       void *memset(void *s, int c, size_t n);

DESCRIPTION
       The memset() function fills the first n bytes of the memory area pointed to by s with the constant byte c.

RETURN VALUE
       The memset() function returns a pointer to the memory area s.

意思是：
s : 填充的內存塊的指標
c : 要設置的值。作為一個int值傳遞，但使用這個值的無符號字符型轉換函數填充的內存塊。
n : 要設置的值的字節數

3/12更新：
最近更新來重新檢視之前上學期寫的一些程式碼，進行程式簡化和自己回答一些自己上述的問題。

首先： 為何不可以使用strdup?

如果將程式碼改為：

list_ele_t *ptr;
  if (q == NULL)
    return false;

  list_ele_t *newh = (list_ele_t *)malloc(sizeof(list_ele_t));
  if (newh == NULL)
    return false;

  //newh->value = (char *)malloc(
      //strlen(s) + 1);
    newh->value = (char *)malloc(
      strlen(s)+ 1 ); //因為s是從0開始要加一才能表示其真正所需的記憶體
  if (!newh->value) {
    free(newh);
    return false;
  }
  newh->value=strdup(s); //將接受的字串指標s傳入newh的value中
  s = NULL;
  
  ptr = q->head;    //將前一個結構位址儲存在ptr中
  newh->next = ptr; //將新創的結構指向之前生成的結構

  if (q->size == 0) {
    q->tail = newh;
  }

會發現strdup會顯示error，但參照規格書後其程式碼是沒有問題的原因是出在function hooking的身上，因為我們在定義free和malloc時，會被定義為test_free和test_malloc，也就是說其外層會包一層macro來保護程式碼不會crash（例如：雙malloc)，而什麼是function hooking呢？我參考了以下的文章：
Function Hooking ，裡面其中提到：Function call hooking refers to a range of techniques used to intercept calls to pre-existing functions and wrap around them to modify the function’s behavior at runtime 所以如果我們想要strdup能夠正常使用的話就必須自己寫strdup的外層macro將其寫在harness.c裡面，例如test_free這樣：

void test_free(void *p)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to free disallowed");
        return;
    }
    if (p == NULL) {
        report(MSG_ERROR, "Attempt to free NULL");
        error_occurred = true;
        return;
    }
    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);

    /* Unlink from list */
    block_ele_t *bn = b->next;
    block_ele_t *bp = b->prev;
    if (bp)
        bp->next = bn;
    else
        allocated = bn;
    if (bn)
        bn->prev = bp;

    free(b);
    allocated_count--;
}

撰寫strdup的封包：

持續更新中…