2018q3 Homework 2(lab0)

contributed by <tony30701>

tags: sysprog2018

• 請補上實驗環境
• add a new file "test.txt" for a commit test 開頭請大寫

課程助教

tony30701收到

預期目標

• 英文閱讀 ( In progress )
• C 語言程式設計基礎
• 準備 GNU/Linux 開發工具 (完成)
• 學習使用 Git 與 GitHub ( In progress )
• 學習效能分析
• 研究自動測試機制

實驗環境

root@ubuntu:~/8_NCKU_SysProg/lab0-c# cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.1 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.1 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/"
UBUNTU_CODENAME=xenial

root@ubuntu:~/8_NCKU_SysProg/lab0-c# cat /proc/version
Linux version 4.4.0-134-generic (buildd@lgw01-amd64-033) (gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.10) ) #160-Ubuntu SMP Wed Aug 15 14:58:00 UTC 2018
root@ubuntu:~/8_NCKU_SysProg/lab0-c#

作業進度

[Okay] q new: Create a new, empty queue.
[Okay] q free: Free all storage used by a queue.
[Okay] q insert head: Attempt to insert a new element at the head of the queue (LIFO discipline).
[Okay] q insert tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
[Okay] q remove head: Attempt to remove the element at the head of the queue.
[Okay] q size: Compute the number of elements in the queue.
[Okay] 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.

測試過程與除錯分析

[1st test by qtest]

root@ubuntu:~/8_NCKU_SysProg/lab0-c# ./qtest
cmd>show
cmd>show
q = NULL
cmd>free
cmd>free
Warning: Calling free on null queue
q = NULL
cmd>new
cmd>new
q = []
cmd>free
cmd>free
q = NULL
cmd>

---

[ 2nd test by qtest ]

在實現 q_insert_tail(queue_t *q, char *s) 的過程中一直很不順利, 主要是因為少了 newt->next = NULL 的關係，導致使用 qtest 在做功能測試的過程一直出現 error message ，在使用 ctag + taglist 的 trace 功能後，發現原因是 qtest 會去 iterate linked list ，而我的 linked list 的 tail node 的 next pointer 不是NULL , 而是一個任意的記憶體空間，導致 qtest 在判斷的過程中發生錯誤，記住此次的錯誤並養成好的coding習慣才不會浪費時間debug。 ––(30/09/2018)

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    if (q->head == NULL){
        return q_insert_head(q, s) ? true : false ;
    }

    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    list_ele_t *newt = malloc(sizeof(list_ele_t));;
    newt->value = malloc(sizeof(char) * (strlen(s) + 1));
    for(int i = 0; i < strlen(s); i++){
        newt->value[i] = s[i];
    }
    newt->value[strlen(s)] = '\0';
    newt->next = NULL;    //Take care of this assignemnt, it's a must-be action as test program would iterate the linked list.
                          //If the NULL is not assigned to newt->next, the test program would make not qualified judge.

    q->tail->next = newt;
    q->tail = newt;

    return true;;
}

root@ubuntu:~/8_NCKU_SysProg/lab0-c# ./qtest
cmd>new
cmd>new
q = []
cmd>it aaa
cmd>it aaa
q->head->value is aaa
q->tail->value is aaa
q->head is NULL, use	q_insert_head() to insert node
q = [aaa]
cmd>it bbb
cmd>it bbb
Length of bbb is 3
q->head->value is aaa
q->tail->value is aaa
q->tail->value is bbb (after insert tail node)
q = [aaa bbb]
cmd>it ccc
cmd>it ccc
Length of ccc is 3
q->head->value is aaa
q->tail->value is bbb
q->tail->value is ccc (after insert tail node)
q = [aaa bbb ccc]
cmd>it ddddd
cmd>it ddddd
Length of ddddd is 5
q->head->value is aaa
q->tail->value is ccc
q->tail->value is ddddd (after insert tail node)
q = [aaa bbb ccc ddddd]
cmd>ih OOO
cmd>ih OOO
q->head->value is OOO
q->tail->value is ddddd
q = [OOO aaa bbb ccc ddddd]
cmd>ih PPP
cmd>ih PPP
q->head->value is PPP
q->tail->value is ddddd
q = [PPP OOO aaa bbb ccc ddddd]
cmd>ih QQQ
cmd>ih QQQ
q->head->value is QQQ
q->tail->value is ddddd
q = [QQQ PPP OOO aaa bbb ccc ddddd]
cmd>it AAA
cmd>it AAA
Length of AAA is 3
q->head->value is QQQ
q->tail->value is ddddd
q->tail->value is AAA (after insert tail node)
q = [QQQ PPP OOO aaa bbb ccc ddddd AAA]
cmd>

---

Git commit 遇到以下錯誤
root@ubuntu:~/8_NCKU_SysProg/lab0-c# git commit
[queue.c:85]: (error) Memory leak: newh
Fail to pass static analysis.

在 trace code 之後發現 git commit 的過程中會去執行下方的 script 是開放源碼的靜態分析工具，可用於分析C/C++的程式。
主要能偵測的有下面幾項：

[1] Out of bounds
[2] Exception safety
[3] Memory leaks
[4] Obsolete functions are used
[5] Invalid usage of STL
[6] Uninitialized variables and unused functions

看來這或許就是我的程式碼為什麼不能完全 Pass 的原因了。

# static analysis
$CPPCHECK $CPPCHECK_OPTS >/dev/null
if [ $? -ne 0 ]; then
    RETURN=1
    echo "" >&2
    echo "Fail to pass static analysis." >&2
    echo
fi

3rd test by qtest (主要針對 trace-06-string 這個 testcase)

下面測試結果有提到說我對於 option length 30 這個指令不太了解，它的意思代表要呈現的 string length 。在這個測項中，其中有兩個指令是 [1]option length 30 [2]rh meerkat_panda_squirrel_vulture 意思就是 qtest 會分配一個 30 byte 的 buffer 來儲存要被刪掉的 head->value (若字串長度過長，多餘的部份就忽視)。而我在 queue.c 的實作中必須把 value 對應的 string 儲存到這個 buffer ，同時 terminator \0 的位置也必須放在正確的位置，否則就會看到如下的 error message (多出了不必要的 'X' 字元或者超出buffer能接收的大小)。

(第1次修正)
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR:  Removed value meerkat_panda_squirrel_vulture_XXXX != expected value meerkat_panda_squirrel_vulture
ERROR:  Removed value aardvark_bear_dolphin_gerbil_XXXXXX != expected value aardvark_bear_dolphin_gerbil
ERROR:  Removed value aardvark_bear_dolphin_XXXXXXXXXXXXX != expected value aardvark_bear_dolphin
ERROR:  Removed value meerkat_panda_squirrel_XXXXXXXXXXXX != expected value meerkat_panda_squirrel
ERROR:  Removed value meerkat_XXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat
Error limit exceeded.  Stopping command execution

(第2次修正)
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
ERROR: copying of string in remove_head overflowed destination buffer.
Error limit exceeded.  Stopping command execution

(最後修正)
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7

error message 對應的程式碼 from qtest.c

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

    if (q == NULL)
        report(3, "Warning: Calling remove head on null queue");
    else if (q->head == NULL)
        report(3, "Warning: Calling remove head on empty queue");
    error_check();
    bool rval = false;
    if (exception_setup(true))
        rval = q_remove_head(q, removes, string_length + 1);
    exception_cancel();
    if (rval) {
        removes[string_length + STRINGPAD] = '\0';
        if (removes[0] == '\0') {
            report(1, "ERROR: Failed to store removed value");
            ok = false;
        } else if (removes[string_length + 1] != 'X') {
            report(1,
                   "ERROR: copying of string in remove_head overflowed "
                   "destination buffer.");
            ok = false;
        } else {
            report(2, "Removed %s from queue", removes);
        }
        qcnt--;
    } else {
        fail_count++;
        if (!check && fail_count < fail_limit) {
            report(2, "Removal from queue failed");
        } else {
            report(1, "ERROR:  Removal from queue failed (%d failures total)",
                   fail_count);
            ok = false;
        }
    }
    if (ok && check && strcmp(removes, checks) != 0) {
        report(1, "ERROR:  Removed value %s != expected value %s", removes,
               checks);
        ok = false;
    }

測試結果

尚有一些測試項目無法完全通過，目前針對 trace-06-string 的測項進行除錯工作，對於測項內使用到 option length 30 的命令不太能夠理解其目的 ––(30/09/2018)

# Test operations on empty queue
# Test remove_head with NULL argument
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
# Test of malloc failure on new
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
# Test of malloc failure on insert_tail
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
# Test performance of insert_tail
# Test performance of size
# Test performance of insert_tail, size, and reverse
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of gerbil failed (1 failures total)
---	Trace		Points
+++ TESTING trace trace-01-ops:
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
---	trace-06-string	0/7
+++ TESTING trace trace-07-robust:
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
---	trace-09-robust	0/7
+++ TESTING trace trace-10-malloc:
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
---	trace-11-malloc	0/7
+++ TESTING trace trace-12-malloc:
---	trace-12-malloc	0/7
+++ TESTING trace trace-13-perf:
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
---	trace-15-perf	0/7
---	TOTAL		65/100

Update

root@ubuntu:~/8_NCKU_SysProg/lab0-c# make test
scripts/driver.py
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---	trace-09-robust	0/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
---	trace-11-malloc	0/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---	trace-12-malloc	0/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		79/100

Update –– 01/10/2018 PM5:10

root@ubuntu:~/8_NCKU_SysProg/lab0-c# make test
scripts/driver.py
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---	trace-05-ops	6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
---	trace-11-malloc	0/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
---	trace-12-malloc	0/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		86/100
root@ubuntu:~/8_NCKU_SysProg/lab0-c#

update –– 02/10/2018

# Test performance of insert_tail
cmdline is (null)
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
cmdline is # Test performance of size

# Test performance of size
cmdline is (null)
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
cmdline is # Test performance of insert_tail, size, and reverse
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	0/7
---	TOTAL		93/100

update –– 02/10/2018

+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---	trace-15-perf	7/7
---	TOTAL		100/100