# 2018q3 Homework2 (lab0)
contributed by < [`butastur-rtos`](https://github.com/butastur-rtos) >
* [Overview](http://www.cs.cmu.edu/afs/cs/academic/class/15513-m18/www/lectures/01-overview.pdf)
* [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* Studying man page
* linked list
* queue
* implements each function
* 探討一下不同的實作品味
* 解釋自動評分系統運作的原理
* 研究自動測試機制
## [Overview](http://www.cs.cmu.edu/afs/cs/academic/class/15513-m18/www/lectures/01-overview.pdf)
* page 22 ~ page 33 在說明作弊這件事, 整份文件只有59頁, 其中10頁在說明作弊的認定和後果, 最毛骨悚然的是第 26 頁的這句話, ==Loss of respect by you, the instructors and your colleagues== [ [ `Overview` ] ](http://www.cs.cmu.edu/afs/cs/academic/class/15513-m18/www/lectures/01-overview.pdf)
* 學習最重要的就是==誠實的面對自己==, 所以這個 homework 會依照==和 CMU 學生同樣標準的Academic Integrity==來撰寫
* 節錄自第27頁
:::info
### This is Cheating:
- Searching the internet with the phrase 15-213, 15213, 213, 18213, malloclab, etc.
- That’s right, just entering it in a search engine
:::
* 不過第 27 頁同樣也有說明什麼是被鼓勵的
:::info
### This is OK (and encouraged):
- Googling a man page for fputs
- Asking a friend for help with gdb
- Asking a TA or course instructor for help, showing them your code, …
- Looking in the textbook for a code example
- Talking about a (high-level) approach to the lab with a classmate
:::
## [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [Union](https://en.wikibooks.org/wiki/C_Programming/Advanced_data_types)
union 的 size 取決於 member 裡 size 最大的 member
```clike
#include <stdio.h>
int main(){
union {
int i;
char c;
} u;
printf("sizeof(char): %ld\r\n", sizeof(char));
printf("sizeof(int): %ld\r\n", sizeof(int));
printf("sizeof(u): %ld\r\n", sizeof(u));
return 0;
}
```
```shell
$ gcc -o union union.c
$ ./union
sizeof(char): 1
sizeof(int): 4
sizeof(u): 4
```
## Study man page
* man malloc
* man free
## linked list
* macro
* union
* list.h
## queue
## implements each function
* $O(1)$
* q_insert_tail
* q_size
* q_remove_head
* q_insert_head
* q_reverse
$O(1)$ 是一個 notation，表示執行的時間是一個常數，不會因為輸入的資料大小而執行的時間有所不同。
因為要在 $O(1)$ 的時間內執行完成 q_insert_tail, 所以在 list 裡一個一個往下找 tail 的作法是不可能的。 [page 4](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 的圖有一個 head 的additional fields, 應該可以在每一次的 q_insert_tail 紀錄 list 裡最後一個 node 的 address, 所以初步的想法是<b>從 head 的 additional fields</b> 開始著手
[ [queue.h] ](https://github.com/butastur-rtos/lab0-c/blob/master/queue.h#L27)
果然，註解有這麼一段話... add more fields...
```clike
typedef struct {
list_ele_t *head; /* Linked list of elements */
/*
You will need to add more fields to this structure
to efficiently implement q_size and q_insert_tail
*/
} queue_t;
```
>中英文字間記得空白
>[name=課程助教][color=red]
* 開發紀錄
先設定 github
```shell
$ ssh-keygen -t rsa -C "butastur@foxmail.com"
```
commit 試一下
```shell
$ git commit
On branch master
Your branch is up-to-date with 'origin/master'.
Changes not staged for commit:
modified: queue.h
no changes added to commit
```
So, use `git add` like:
```shell
$ git add queue.h
```
* commit 之前, study 一下 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
再 commit 試試
```shell=
$ git commit -m "add fields to point to the tail"
add fields to point to the tail [line 1]
- Capitalize the subject line
Proceed with commit? [e/n/?] e
add fields to point to the tail [line 1]
- Capitalize the subject line
Proceed with commit? [e/n/?] y
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
e - edit commit message
n - abort commit
? - print help
Proceed with commit? [e/n/?] ?
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
e - edit commit message
n - abort commit
? - print help
Proceed with commit? [e/n/?] e
[master 23f7113] Add fields to point to the tail
```
第4行輸入 e，可以編輯 message
第7行輸入 y，因為 y 不是有效選項, 所以出現 help
第17行輸入 e, 再次編輯 message, 因為 message 有限制標題開頭要大寫
:::danger
commit 還是失敗, 所以依照 git 的提示再試一下
git config --global --edit
git commit --amend --reset-author
:::
```shell
Your name and email address were configured automatically based
on your username and hostname. Please check that they are accurate.
You can suppress this message by setting them explicitly. Run the
following command and follow the instructions in your editor to edit
your configuration file:
git config --global --edit
After doing this, you may fix the identity used for this commit with:
git commit --amend --reset-author
1 file changed, 1 insertion(+)
```
commit 之前修改一下 message
``` shell
$ git commit
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
```
看起來, 應該要執行 `git push` 才對
```shell
$ git push
Username for 'https://github.com': butastur-rtos
Password for 'https://butastur-rtos@github.com':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 324 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To https://github.com/butastur-rtos/lab0-c.git
7251dad..b119f00 master -> master
```
:::info
將 git repository 的 https 改為 ssh，並且設定好 ssh-key，之後 git push 就不需要輸入帳號密碼
參照 [更換遠端伺服器倉庫網址](https://gist.github.com/fokayx/255b228ded2bca1c4f60)
:notes: jserv
:::
#### 接下來實作 function q_size
`int q_size(queue_t *q)` 由於要在 $O(1)$ 的常數時間內執行完成, 所以也不可能每次都遍歷整個 list 來取得 queue 的大小,
[`queue.h`](https://github.com/butastur-rtos/lab0-c/blob/master/queue.h#L30)的註解有寫You will need to add more fields to this structure to efficiently implement q_size and q_insert_tail
所以, 增加 <b>int size</b> 到typedef struct queue_t
```clike
typedef struct {
list_ele_t *head; /* Linked list of elements */
/*
You will need to add more fields to this structure
to efficiently implement q_size and q_insert_tail
*/
list_ele_t *tail;
int size;
} queue_t;
```
接下來修改 q_size 的傳回值, 改成傳回q->size
```shell
$ git commit -m "Change q_size return value to q->size"
--- .merge_file_Iu0bic 2018-09-21 13:33:12.940675156 -0500
+++ /tmp/.merge_file_Iu0bic.rV006h 2018-09-21 13:33:12.953675156 -0500
@@ -70,7 +70,7 @@ 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 */
- list_ele_t *newt; // newt means new tail
+ list_ele_t *newt; // newt means new tail
newt = malloc(sizeof(list_ele_t));
q->tail = newt;
return true;
[!] queue.c does not follow the consistent coding style.
Make sure you indent as the following:
clang-format -i queue.c
```
:::danger
格式不對, 所以 commit 失敗
:::
依 git 指示執行 `clang-format` 後再重新 `git add`, 然後再 `git commit`, `git push`
```shell
$ clang-format -i queue.c
$ git add queue.c
$ git commit -m "Change q_size return value to q->size"
[master d923e13] Change q_size return value to q->size
1 file changed, 7 insertions(+), 2 deletions(-)
git push
Username for 'https://github.com': butastur-rtos
Password for 'https://butastur-rtos@github.com':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 419 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To https://github.com/butastur-rtos/lab0-c.git
8c93ea5..d923e13 master -> master
```
#### 接下來實作 q_remove_head
Remove one element, so the size should decrease, 第6行把size減一
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
q->head = q->head->next;
/* remove one element, so the size should decrease */
q->size--;
return true;
}
```
```shell
$ git commit -m "Remove one elem, q_remove_head decrease q->size"
[master 67b3062] Remove one elem, q_remove_head decrease q->size
1 file changed, 2 insertions(+)
$ git push
Username for 'https://github.com': butastur-rtos
Password for 'https://butastur-rtos@github.com':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 386 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To https://github.com/butastur-rtos/lab0-c.git
d923e13..67b3062 master -> master
```
:::info
應該先用 `qtest` 測試過
:notes: jserv
:::
:::info
避免用 `git commit -m`，設定好 $EDITOR 環境變數，用你偏好的編輯器寫好 git commit messages
:notes: jserv
:::
### q_insert_head
q_insert_head的parameter q如果是NULL, 要傳回false
```clike
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
...
}
```
```shell
$ git add queue.c
$ git commit -m "In q_insert_head, if q == NULL, return false"
[master 3a7d956] In q_insert_head, if q == NULL, return false
1 file changed, 4 insertions(+)
$git push
Username for 'https://github.com': butastur-rtos
Password for 'https://butastur-rtos@github.com':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 362 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To https://github.com/butastur-rtos/lab0-c.git
67b3062..3a7d956 master -> master
```
### q_new
initialize a new queue, if malloc return NULL q_new return NULL
```clike
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? if malloc return NULL q_new return NULL */
if (q != NULL) {
q->head = NULL;
/* size initialize to zero */
q->size = 0;
/* tail initialize to NULL */
q->tail = NULL;
}
return q;
}
```
```shell
To https://github.com/butastur-rtos/lab0-c.git
3a7d956..c96f697 master -> master
```
q_remove_head須要Return false if queue is NULL or empty
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if(q == NULL || q->size == 0)
return false;
...
}
```
```shell
$ git add queue.c
$ git commit -m "For remove_head,return false if queue [NULL|empty]"
[master c7484a8] For remove_head,return false if queue [NULL|empty]
1 file changed, 10 insertions(+), 4 deletions(-)
$ git push
Username for 'https://github.com': butastur-rtos
Password for 'https://butastur-rtos@github.com':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 456 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To https://github.com/butastur-rtos/lab0-c.git
c96f697..c7484a8 master -> master
```
### q_free
:::warning
是不是 prev->value 也要 free?
:::
> 這點我也很好奇，但我在釋放 `prev` 的記憶體空間前先釋放 `prev->value` 的記憶體空間卻出現以下錯誤訊息：
> ```shell
> ERROR: Attempt to free unallocated or corrupted block.
> ```
> [name=Lawrence][time=Sun, Sep 23, 2018 3:56 PM]
>> 我也是碰到一樣的 ERROR, 因為 prev->value 是透過 strdup 取得 a pointer to a new string, 原本好奇會不會是因為這樣所以不能 free, 於是查了一下 man, 查到這一段
> 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).
所以我還需要再研究一下要不要 free(prev->value)
> [name=butastur-rtos][time=Sun, Sep 23, 2018 5:31 PM]
> > 是 strdup 惹的禍，因為 harness.h 有段 macro 會把 free 換成一個自己開發的函式，導致你用不到真正的 free ，變成在用 malloc 與 test_free ，因此直接用 malloc 讓 preprocessor 把它也轉成 test_malloc 就好了。
> > [name=pjchiou] [time=2018 Sep 27 Thu 05:58]
>>> 我試一下用 malloc
>>> [name=butastur-rtos] [time=2018 Sep 27 Thu 08:43]
```clike
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
list_ele_t *pos;
for (pos = q->head; pos != NULL;) {
list_ele_t *prev = pos;
pos = pos->next;
free(prev);
}
free(q);
}
```
```shell
$ git add queue.c
$ git commit -m "Implement q_free, free all storage used by queue"
[master 0e7a011] Implement q_free, free all storage used by queue
1 file changed, 6 insertions(+)
$ git push
Username for 'https://github.com': butastur-rtos
Password for 'https://butastur-rtos@github.com':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 411 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To https://github.com/butastur-rtos/lab0-c.git
c7484a8..0e7a011 master -> master
```
### q_size
修改 q_size 的傳回值
```clike
int q_size(queue_t *q)
{
return q != NULL ? q->size : 0;
}
```
```shell
$ git commit -m "Implement q_size, return 0 if q is NULL or empty"
```
```shell
$ git commit -m "Change insert_head, insert_tail logical"
```
```shell
$ git commit -m "Use free to free storage for q_free"
```
```shell
$ git commit -m "When free a NULL queue, just do nothing"
```
### q_reverse
[ [ source ] ](https://github.com/butastur-rtos/lab0-c/blob/master/queue.h)
```clike
/* Linked list element (You shouldn't need to change this) */
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;
...
/*
Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
It should rearrange the existing ones.
*/
void q_reverse(queue_t *q);
```
實作 q_reverse 要注意兩點, 第一, 不可以增加 list_ele_t的欄位來作雙方鏈結, 第二, 不可以對 list 的 element 作allocate or free, 只可以 rearrange the existing ones.
初期的想法是分兩個步驟:
第一, <b>從 tail 開始, 每一個 list_ele_t 的 next 都指向前一個 list_ele_t</b>
第二, <b>等每一個 list_ele_t 的 next 都指向前一個之後, swap q->head 和 q->tail</b>
以上兩個步驟好像太普通，我想試試以下這個方法, 節錄自 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L504)
[ [`source`] ](https://github.com/torvalds/linux/blob/master/include/linux/list.h#L504)
```clike
/**
* list_for_each_entry_reverse - iterate backwards over list of given type.
* @pos: the type * to use as a loop cursor.
* @head: the head for your list.
* @member: the name of the list_head within the struct.
*/
#define list_for_each_entry_reverse(pos, head, member) \
for (pos = list_last_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_prev_entry(pos, member))
```
:::danger
不過再仔細看一下, 這個方法不行, 因為這是用在 doubly linked list
:::
如果用以下的順序, 寫出來會更糟或是一般般呢? 先畫成 Graph 思考一下
```graphviz
digraph G {
rankdir=LR;
subgraph cluster_11 {
label=Step11;
color=black;
node [style=filled,color=lightgrey,shape=record];
k2 -> k1; k3 -> k2; k1->k0;
}
subgraph cluster_10 {
label=Step10;
color=black;
node [style=filled,color=lightgrey,shape=record];
j2 -> j1; j3 -> j2; j1->j0;
}
subgraph cluster_9 {
label=Step9;
color=black;
node [style=filled,color=lightgrey,shape=record];
i0 -> i1; i2 -> i1; i3 -> i2; i1->i0;
}
subgraph cluster_8 {
label=Step8;
color=black;
node [style=filled,color=lightgrey,shape=record];
h0 -> h1; h2 -> h1; h3 -> h2;
}
subgraph cluster_7 {
label=Step7;
color=black;
node [style=filled,color=lightgrey,shape=record];
g0 -> g1 -> g2 -> g1; g3 -> g2;
}
subgraph cluster_6 {
label=Step6;
color=black;
node [style=filled,color=lightgrey,shape=record];
f0 -> f1 -> f2; f3 -> f2;
}
subgraph cluster_5 {
label=Step5;
color=black;
node [style=filled,color=lightgrey,shape=record];
e0 -> e1 -> e2; e3 -> e2;
}
subgraph cluster_4 {
label=Step4;
color=black;
node [style=filled,color=lightgrey,shape=record];
d0 -> d1 -> d2 -> d3 -> d2;
}
subgraph cluster_3 {
label=Step3;
color=black;
node [style=filled,color=lightgrey,shape=record];
c0 -> c1 -> c2 -> c3;
}
subgraph cluster_1 {
label=Step1;
color=black;
node [style=filled,color=lightgrey,shape=record];
a0 -> a1 -> a2 -> a3;
}
prev_a -> a0;
head_a -> a0;
tail_a -> a3
a3 -> NULL_a;
head_c -> c0;
prev_c -> c2;
tail_c -> c3;
c3 -> NULL_c;
head_d -> d0;
prev_d -> d2;
tail_d -> d3;
head_e -> e0;
prev_e -> e0;
tail_e -> e3;
e2 -> NULL_e;
head_f -> f0;
prev_f -> f1;
tail_f -> f3;
f2 -> NULL_f;
prev_g -> g1;
head_g -> g0;
tail_g -> g3;
head_h -> h0;
prev_h -> h0;
tail_h -> h3;
h1 -> NULL_h;
head_i -> i0;
prev_i -> i0;
tail_i -> i3;
head_j -> j0;
prev_j -> j0;
tail_j -> j3;
j0 -> NULL_j;
head_k -> k3;
prev_k -> k3;
tail_k -> k0;
k0 -> NULL_k;
tail_a [shape=plaintext,label=tail];
tail_c [shape=plaintext,label=tail];
tail_d [shape=plaintext,label=tail];
tail_e [shape=plaintext,label=tail];
tail_f [shape=plaintext,label=tail];
tail_g [shape=plaintext,label=tail];
tail_h [shape=plaintext,label=tail];
tail_i [shape=plaintext,label=tail];
tail_j [shape=plaintext,label=tail];
tail_k [shape=plaintext,label=tail];
head_a [shape=plaintext,label=head];
head_c [shape=plaintext,label=head];
head_d [shape=plaintext,label=head];
head_e [shape=plaintext,label=head];
head_f [shape=plaintext,label=head];
head_g [shape=plaintext,label=head];
head_h [shape=plaintext,label=head];
head_i [shape=plaintext,label=head];
head_j [shape=plaintext,label=head];
head_k [shape=plaintext,label=head];
prev_a [shape=plaintext,label=prev];
prev_c [shape=plaintext,label=prev];
prev_d [shape=plaintext,label=prev];
prev_e [shape=plaintext,label=prev];
prev_f [shape=plaintext,label=prev];
prev_g [shape=plaintext,label=prev];
prev_h [shape=plaintext,label=prev];
prev_i [shape=plaintext,label=prev];
prev_j [shape=plaintext,label=prev];
prev_k [shape=plaintext,label=prev];
NULL_a [shape=plaintext,label=NULL];
NULL_c [shape=plaintext,label=NULL];
NULL_e [shape=plaintext,label=NULL];
NULL_f [shape=plaintext,label=NULL];
NULL_h [shape=plaintext,label=NULL];
NULL_j [shape=plaintext,label=NULL];
NULL_k [shape=plaintext,label=NULL];
c0[label=a0];
c1[label=a1];
c2[label=a2];
c3[label=a3];
d0[label=a0];
d1[label=a1];
d2[label=a2];
d3[label=a3];
e0[label=a0];
e1[label=a1];
e2[label=a2];
e3[label=a3];
f0[label=a0];
f1[label=a1];
f2[label=a2];
f3[label=a3];
g0[label=a0];
g1[label=a1];
g2[label=a2];
g3[label=a3];
h0[label=a0];
h1[label=a1];
h2[label=a2];
h3[label=a3];
i0[label=a0];
i1[label=a1];
i2[label=a2];
i3[label=a3];
j0[label=a0];
j1[label=a1];
j2[label=a2];
j3[label=a3];
k0[label=a0];
k1[label=a1];
k2[label=a2];
k3[label=a3];
}
```
==如果用這個方法, 寫出來會更糟或是一般般呢?== 繼續實驗...
```clike
void q_reverse(queue_t *q)
{
if (q != NULL && q->size && q->tail != NULL) {
list_ele_t *prev;
while (q->head != NULL
&& q->head->next != NULL
&& q->head->next->next != q->head) {
prev = q->head;
while (prev->next != NULL && prev->next->next != NULL)
prev = prev->next;
if (prev->next != NULL && prev->next->next == NULL) {
prev->next->next = prev;
prev->next = NULL;
}
}
q->head->next = NULL;
q->head = q->tail;
q->tail = prev;
prev = q->head;
}
}
```
`qtest` 測試的結果是
```shell
$ ./qtest
cmd>new
cmd>new
q = []
cmd>ih a0
cmd>ih a0
q = [a0]
cmd>ih a1
cmd>ih a1
q = [a1 a0]
cmd>ih a2
cmd>ih a2
q = [a2 a1 a0]
cmd>ih a3
cmd>ih a3
q = [a3 a2 a1 a0]
cmd>reverse
cmd>reverse
q = [a0 a1 a2 a3]
```
`make test` 的結果是
```shell
+++ 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
```
:::danger
但是這樣寫的效能太差, 所以 Time limit exceeded, ~~這樣寫會導致效能慢也是可以預期的, 畢竟每次找prev都是從頭開始找~~
:::
```shell
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
--- trace-13-perf 0/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
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
--- trace-15-perf 0/7
--- TOTAL 86/100
```
:::danger
由於效能太差, 所以要思考一下有什麼改善的方法?
:::
> 或許可以不只用`prev`，多用幾個 pointers 記錄
> [name=Lawrence][time=Sun, Sep 23, 2018 3:50 PM]
>> 多用兩個 pointer 果然有效
>> [name=butastur-rtos][time=Thu, Sep 27, 2018 8:46 PM]
<br>
<b>如果用以下的流程?</b>
```graphviz
digraph G {
rankdir=LR;
subgraph cluster_10 {
label=Step10;
color=black;
node [style=filled,color=lightgrey,shape=record];
a1_10 -> a0_10; a2_10 -> a1_10; a3_10;
}
subgraph cluster_9 {
label=Step9;
color=black;
node [style=filled,color=lightgrey,shape=record];
a1_9 -> a0_9; a2_9 -> a1_9; a3_9;
}
subgraph cluster_8 {
label=Step8;
color=black;
node [style=filled,color=lightgrey,shape=record];
a0_8 -> a1_8 -> a0_8; a2_8 -> a1_8; a3_8;
}
subgraph cluster_7 {
label=Step7;
color=black;
node [style=filled,color=lightgrey,shape=record];
g0_7 -> g1_7 -> g0_7; g2_7 -> g1_7; g3_7;
}
subgraph cluster_6 {
label=Step6;
color=black;
node [style=filled,color=lightgrey,shape=record];
f0_6 -> f1_6 -> f0_6; f2_6 -> f3_6;
}
subgraph cluster_4 {
label=Step4;
color=black;
node [style=filled,color=lightgrey,shape=record];
a0_4 -> a1_4 -> a0_4; a2_4 -> a3_4;
}
subgraph cluster_3 {
label=Step3;
color=black;
node [style=filled,color=lightgrey,shape=record];
d0 -> d1 -> d2 -> d3;
}
subgraph cluster_2 {
label=Step2;
color=black;
node [style=filled,color=lightgrey,shape=record];
c0 -> c1 -> c2 -> c3;
}
subgraph cluster_1 {
label=Step1;
color=black;
node [style=filled,color=lightgrey,shape=record];
a0 -> a1 -> a2 -> a3;
}
prev_a -> a0;
head_a -> a0;
tail_a -> a3
a3 -> NULL_a;
head_c -> c0;
prev_c -> c0;
tail_c -> c1;
c3 -> NULL_c;
head_3 -> d0;
prev_3 -> d0;
tail_3 -> d2;
d3 -> NULL_d;
head_4 -> a0_4;
prev_4 -> a0_4;
tail_4 -> a2_4;
a3_4 -> NULL_4;
head_f -> f0_6;
prev_f -> f1_6;
tail_f -> f2_6;
f3_6 -> NULL_f;
prev_g -> g2_7;
head_g -> g0_7;
tail_g -> g3_7;
g3_7 -> NULL_g;
prev_8 -> a2_8;
head_8 -> a0_8;
tail_8 -> a3_8;
a3_8 -> a2_8;
prev_9 -> a2_9;
head_9 -> a0_9;
tail_9 -> a3_9;
a3_9 -> a2_9;
a0_9 -> NULL_9;
prev_10 -> a2_10;
tail_10 -> a0_10;
head_10 -> a3_10;
a3_10 -> a2_10;
a0_10 -> NULL_10;
tail_a [shape=plaintext,label=tail];
tail_c [shape=plaintext,label=tail];
tail_3 [shape=plaintext,label=tail];
tail_4 [shape=plaintext,label=tail];
tail_f [shape=plaintext,label=tail];
tail_g [shape=plaintext,label=tail];
tail_8 [shape=plaintext,label=tail];
tail_9 [shape=plaintext,label=tail];
tail_10 [shape=plaintext,label=tail];
head_a [shape=plaintext,label=head];
head_c [shape=plaintext,label=head];
head_3 [shape=plaintext,label=head];
head_4 [shape=plaintext,label=head];
head_f [shape=plaintext,label=head];
head_g [shape=plaintext,label=head];
head_8 [shape=plaintext,label=head];
head_9 [shape=plaintext,label=head];
head_10 [shape=plaintext,label=head];
prev_a [shape=plaintext,label=prev];
prev_c [shape=plaintext,label=prev];
prev_3 [shape=plaintext,label=prev];
prev_4 [shape=plaintext,label=prev];
prev_f [shape=plaintext,label=prev];
prev_g [shape=plaintext,label=prev];
prev_8 [shape=plaintext,label=prev];
prev_9 [shape=plaintext,label=prev];
prev_10 [shape=plaintext,label=prev];
NULL_a [shape=plaintext,label=NULL];
NULL_c [shape=plaintext,label=NULL];
NULL_d [shape=plaintext,label=NULL];
NULL_4 [shape=plaintext,label=NULL];
NULL_f [shape=plaintext,label=NULL];
NULL_g [shape=plaintext,label=NULL];
NULL_9 [shape=plaintext,label=NULL];
NULL_10 [shape=plaintext,label=NULL];
c0[label=a0];
c1[label=a1];
c2[label=a2];
c3[label=a3];
d0[label=a0];
d1[label=a1];
d2[label=a2];
d3[label=a3];
a0_4[label=a0];
a1_4[label=a1];
a2_4[label=a2];
a3_4[label=a3];
f0_6[label=a0];
f1_6[label=a1];
f2_6[label=a2];
f3_6[label=a3];
g0_7[label=a0];
g1_7[label=a1];
g2_7[label=a2];
g3_7[label=a3];
a0_8[label=a0];
a1_8[label=a1];
a2_8[label=a2];
a3_8[label=a3];
a0_9[label=a0];
a1_9[label=a1];
a2_9[label=a2];
a3_9[label=a3];
a0_10[label=a0];
a1_10[label=a1];
a2_10[label=a2];
a3_10[label=a3];
}
```
:::info
上面這個流程只用一個 `prev` 並沒有辦法完成, 所以看起來加一個 `prev` 不夠, 如 Lawrence 建議再加2個 pointers 試試看, 一個 `current`, 代表 `prev` 的下一個, 一個 `next`, 指向 `current` 的下一個
:::
:::info
先將目前進度 commit
:::
```shell
$ clang-format -i queue.c
$ git add queue.c
$ git commit --amend
[master 85ee74b] Implement q_reverse
Date: Fri Sep 21 21:07:13 2018 -0500
1 file changed, 27 insertions(+), 2 deletions(-)
$ git push origin master --force
Enter passphrase for key '/root/.ssh/id_rsa':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 986 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To github.com:butastur-rtos/lab0-c.git
+ cd8dc61...85ee74b master -> master (forced update)
```
:::info
使用3個 pointers 來紀錄 element of list 後效能有提升
:::
```clike
void q_reverse(queue_t *q)
{
if (q != NULL && q->size) {
list_ele_t *prev, *current, *next;
prev = q->head;
current = q->head->next;
next = q->head->next->next;
prev->next = NULL;
current->next = prev;
while (next != NULL) {
prev = current;
current = next;
next = next->next;
current->next = prev;
}
q->tail = q->head;
q->head = current;
}
}
```
```shell
+++ 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 93/100
```
```shell
To https://github.com/butastur-rtos/lab0-c.git
+ 85ee74b...cda8046 master -> master (forced update)
```
:::info
#### 設定 git 使用 SSH Key, 免得每次 commit 都要敲 username, password
:::
設定SSH, 然後使用 vim 編輯 message 後再 commit
```shell
$ git commit --amend
[master cd8dc61] Meet remove_head requirement
Date: Fri Sep 21 21:07:13 2018 -0500
1 file changed, 9 insertions(+), 2 deletions(-)
$ git push origin master --force
Enter passphrase for key '/root/.ssh/id_rsa':
ERROR: The key you are authenticating with has been marked as read only.
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.
root@ut:~/temp/ssh/lab0-c#
```
所以 github 上的 authenticating 要再改一下
```shell
$ git push origin master --force
Enter passphrase for key '/root/.ssh/id_rsa':
Counting objects: 3, done.
Delta compression using up to 2 threads.
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 603 bytes | 0 bytes/s, done.
Total 3 (delta 2), reused 0 (delta 0)
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To github.com:butastur-rtos/lab0-c.git
+ 81d7a17...cd8dc61 master -> master (forced update)
```
:::info
q_reverse 在不使用 doubly linked list 的前提下, 試過以現有的q->head, q->tail來實作, 但是效能太低, 試過只加一個 pointer prev 來實作, 但是程式複雜度提高, 最後加了3個pointers prev, current, next 這三個pointer, 在對每一個 element 作 reverse 的時候, 來紀錄 element 的前後兩個 element 的address, 最後解決了這個效能的問題, 這個解法是在不使用 doubly linked list 的前提下, 網路上常見的寫法
:::
:::danger
以下這個 error, 會使用 `qtest` 來 debug, 並用這個 error 來說明 `qtest`
:::
```shell
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
--- trace-06-string 0/7
```
看一下 trace-06-string 作了什麼測試
```shell=
$ cat traces/trace-06-string.cmd
# Test of truncated strings
option fail 0
option malloc 0
new
ih aardvark_bear_dolphin_gerbil_jaguar 5
it meerkat_panda_squirrel_vulture_wolf 5
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
option length 30
rh meerkat_panda_squirrel_vulture
reverse
option length 28
rh aardvark_bear_dolphin_gerbil
option length 21
rh aardvark_bear_dolphin
reverse
option length 22
rh meerkat_panda_squirrel
option length 7
rh meerkat
reverse
option length 8
rh aardvark
option length 100
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
free
```
```shell
$ ./qtest
...
cmd>rh aardvark_bear_dolphin_gerbil_jaguar
Removed aardvark_bear_dolphin_gerbil_jaguar from queue
q = [meerkat_panda_squirrel_vulture_wolf]
cmd>reverse
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
q = [meerkat_panda_squirrel_vulture_wolf ... ]
```
一步一步的執行, 直到==第28行==的 reverse 產生一個 Segmentation fault, 所以從 q_reverse 來檢查一下
在第 4 行加上 NULL 的判斷
```clike=
void q_reverse(queue_t *q)
{
if (q != NULL && q->size) {
if(q->head->next == NULL){
return;
}
...
}
...
}
```
測試結果
```shell=
$ make test
...
--- trace-15-perf 7/7
--- TOTAL 100/100
```
:::danger
目前實作碼的品味不夠, 在9/27(四)之前應該要再把目前的實作碼改的比較有品味
> [name=butastur-rtos]
:::
### 使用工具來分析 q_reverse 的效能
* $O(n)$
* valgrind
用 `valgrind` 來檢查一下 [`qtest`](https://github.com/butastur-rtos/lab0-c/blob/master/queue.c) 的執行結果有沒有 memory leak
```shell
$ valgrind ./qtest
cmd>new
cmd>new
q = []
cmd>ih str 1000
cmd>ih str 1000
q = [str str str str str str str str str str str str str str str str str str str str str str str str str str str str str str ... ]
cmd>quit
cmd>quit
Freeing queue
==18771==
==18771== HEAP SUMMARY:
==18771== in use at exit: 4,000 bytes in 1,000 blocks
==18771== total heap usage: 2,041 allocs, 1,041 frees, 70,190 bytes allocated
==18771==
==18771== LEAK SUMMARY:
==18771== definitely lost: 4,000 bytes in 1,000 blocks
==18771== indirectly lost: 0 bytes in 0 blocks
==18771== possibly lost: 0 bytes in 0 blocks
==18771== still reachable: 0 bytes in 0 blocks
==18771== suppressed: 0 bytes in 0 blocks
==18771== Rerun with --leak-check=full to see details of leaked memory
==18771==
==18771== For counts of detected and suppressed errors, rerun with: -v
==18771== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
```
對 `valgrind` 多一些嘗試, 試一下 `valgrind --leak-check=full`
```shell
$ valgrind --leak-check=full ./qtest
==18783== Memcheck, a memory error detector
==18783== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==18783== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==18783== Command: ./qtest
==18783==
cmd>new
cmd>new
q = []
cmd>ih str 1000
cmd>ih str 1000
q = [str str str str str str str str str str str str str str str str str str str str str str str str str str str str str str ... ]
cmd>quit
cmd>quit
Freeing queue
==18783==
==18783== HEAP SUMMARY:
==18783== in use at exit: 4,000 bytes in 1,000 blocks
==18783== total heap usage: 2,036 allocs, 1,036 frees, 70,141 bytes allocated
==18783==
==18783== 4,000 bytes in 1,000 blocks are definitely lost in loss record 1 of 1
==18783== at 0x4C2BBAF: malloc (vg_replace_malloc.c:299)
==18783== by 0x4EB83B9: strdup (strdup.c:42)
==18783== by 0x10D1E0: q_insert_head (queue.c:75)
==18783== by 0x10968C: do_insert_head (qtest.c:166)
==18783== by 0x10BB68: interpret_cmda (console.c:218)
==18783== by 0x10BBFC: interpret_cmd (console.c:239)
==18783== by 0x10CA14: cmd_select (console.c:605)
==18783== by 0x10CB67: run_console (console.c:642)
==18783== by 0x10A77D: main (qtest.c:573)
==18783==
==18783== LEAK SUMMARY:
==18783== definitely lost: 4,000 bytes in 1,000 blocks
==18783== indirectly lost: 0 bytes in 0 blocks
==18783== possibly lost: 0 bytes in 0 blocks
==18783== still reachable: 0 bytes in 0 blocks
==18783== suppressed: 0 bytes in 0 blocks
==18783==
==18783== For counts of detected and suppressed errors, rerun with: -v
==18783== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
```
:::info
說明 `qtest` 的行為
> [name=butastur-rtos]
:::
<hr>
### 目前的進度
```shell
$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
--- 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
```
:::info
100/100 PASS
:::
## 解釋自動評分系統運作的原理
* qtest 如何 detect corruption
* 說明 qtest 的行為
### qtest 如何 detect corruption
* What is Corruption detected?
qtest detect 到 corruption 時會出現以下 訊息, 接著說明 qtest 是如何辦到這件事的
```shell
# Test performance of insert_tail, size, and reverse
ERROR: Attempted to free unallocated or corrupted block. Address = 0x561698e80580
ERROR: Corruption detected in block with address 0x561698e80580 when attempting to free it
*** Error in `./qtest': free(): invalid next size (fast): 0x0000561698e80560 ***
```
qtest 在 free 的時候, 實際上是執行 test_free, 這個 function 會呼叫 find_header, find_footer, 通過判斷 block 的 footer, 如果不是 [<b>0xbeefdead</b>(也就是MAGICFOOTER)](https://github.com/butastur-rtos/lab0-c/blob/master/harness.c#L23), 就會被視為 Corruption detected
接下來解釋 block, footer, 以及說明 test_malloc, find_header, find_footer 彼此之間是如何動作的
[ [`harness.c`] ](https://github.com/butastur-rtos/lab0-c/blob/master/harness.c#L35)
```clike
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;
...
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
```
大致上, test_malloc 的時候除了會 allocate 一段預定大小的記憶體之外, 會另外 allocate 一段記憶體 for <b>block_ele_t</b>
:::info
但是另外再 allocate `sizeof(size_t)` 是為了什麼呢?
:::
test_malloc 在==成功== allocate 一段位址後, 會作以下 6 件事
1. assign MAGICHEADER 給 new_block->magic_header
2. assign 預定 allocate size 這個數字給 new_block->payload_size
3. 透過 find_footer 取得 footer 的位址, 這個位址代表這個struct的最底部的位址, 並不能單純透過 new_block->magic_header 這種方法取得, 所以要透過 find_footer
4. 在 footer 的位址放 MAGICFOOTER。這就是 test_malloc 會另外再 allocate `sizeof(size_t)` 的原因, ==因為要放 MAGICFOOTER==
5. 把這個block insert 到list的最前面
6. 傳回 new_block->payload 的位址, ==這就是 allocate 所得到的位址==
[ [`source`] ](https://github.com/butastur-rtos/lab0-c/blob/master/harness.c#L136)
```clike
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
```
```clike
/* Given pointer to block, find its footer */
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;
}
```
:::info
* find_footer 是用來找出 footer of block
* footer of block 如果不是 MAGICFOOTER, 就會觸發一個 error event
* 由於 malloc 所得到的位址實際上是透 test_malloc 所得到, 所以要先用 find_header 取得 pointer to block_ele_t (也就是 block_ele_t *b), 再用 pointer to block_ele_t 取得 footer (也就是 *find_footer(b))
:::
[ [`source`] ](https://github.com/butastur-rtos/lab0-c/blob/master/harness.c#L161)
```clike
block_ele_t *b = find_header(p);
size_t footer = *find_footer(b);
```
### 說明 qtest 的行為
* console.c
* qtest.c
#### console.c
* run_console
* add_cmd
#### qtest.c
* run_console
* do_xxx
* q_xxx
* show_queue
## 研究自動測試機制
* TDD
* Unit Test
## 提問
:::info
自動測試機制是否可以理解為 TDD?
:::
## 實驗環境
```shell
$ cat /etc/os-release
PRETTY_NAME="Debian GNU/Linux 9 (stretch)"
NAME="Debian GNU/Linux"
VERSION_ID="9"
VERSION="9 (stretch)"
ID=debian
HOME_URL="https://www.debian.org/"
SUPPORT_URL="https://www.debian.org/support"
BUG_REPORT_URL="https://bugs.debian.org/"
$ cat /proc/version
Linux version 2.6.32-042stab133.1 (root@kbuild-rh6-x64.eng.sw.ru) (gcc version 4.4.7 20120313 (Red Hat 4.4.7-18) (GCC) ) #1 SMP Thu Aug 16 13:14:51 MSK 2018
$ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 44
model name : Intel(R) Xeon(R) CPU E5630 @ 2.53GHz
stepping : 2
microcode : 21
cpu MHz : 2533.628
cache size : 12288 KB
physical id : 1
siblings : 8
core id : 0
cpu cores : 4
apicid : 32
initial apicid : 32
fpu : yes
fpu_exception : yes
cpuid level : 11
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good eagerfpu xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 popcnt aes lahf_lm ida arat dtherm pti retpoline tpr_shadow vnmi flexpriority ept vpid
bogomips : 5067.25
clflush size : 64
cache_alignment : 64
address sizes : 40 bits physical, 48 bits virtual
power management:
processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 44
model name : Intel(R) Xeon(R) CPU E5630 @ 2.53GHz
stepping : 2
microcode : 21
cpu MHz : 2533.628
cache size : 12288 KB
physical id : 0
siblings : 8
core id : 0
cpu cores : 4
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 11
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good eagerfpu xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 popcnt aes lahf_lm ida arat dtherm pti retpoline tpr_shadow vnmi flexpriority ept vpid
bogomips : 5066.57
clflush size : 64
cache_alignment : 64
address sizes : 40 bits physical, 48 bits virtual
power management:
```
:::danger
持續更新中...
:::
###### tags: `sysprog2018`
Sign in with Wallet
Connect another wallet